Erasure channel modelling–based secure bit allocation schemes for multipath routing in wireless sensor networks

Abstract

In this article, we study secure multipath routing with energy efficiency for a wireless sensor network in the presence of eavesdroppers. We consider two objectives: (1) the multipath routing scheme for maximising the energy efficiency with security constraints and (2) the multipath routing scheme for maximising the secrecy capacity. The binary erasure channel model is adopted to describe the wireless channel states among neighbouring nodes. Based on the binary erasure channel model, the problem of multipath routing degrades to a problem of bit allocation for each path. We formulate the problems and find that the problems are both quasi-convex. For the first one, it is a linear fractional optimisation problem. The optimal solution is obtained by the Charnes–Cooper transformation. For the second one, we propose an iterative algorithm to obtain the $\eta$ -optimal solution. The performance analysis shows that the probability of the secure bit allocation increases along with the number of multipaths and decreases along with the number of hops per path and eavesdroppers. Simulation results are presented to illustrate the proposed algorithms.

Introduction

Background

Multipath routing in multihop networks has been extensively studied for distributed sensor networks. ¹ There are various advantages of multipath routing in wireless sensor networks (WSNs), such as load-balancing, reliability enhancement, and quality of service (QoS) improvement. ² In order to reduce the end-to-end delay and routing overheads, Marina and Das ³ proposed the ad hoc on-demand multipath distance routing protocol (AOMDV), which is a multipath extension to the ad hoc on-demand distance routing protocol (AODV). Split multipath routing (SMR) was proposed to utilise available network resources efficiently and prevent nodes of the route from being congested in heavily loaded traffic situation. ⁴ Multipath routing together with diversity coding has been adopted to guarantee the probability of reconstructing the original information received at the destination. ⁵ In spite of these benefits, multipath routing is less energy efficient than single-path routing, since more intermediate nodes participate into transmissions.

Moreover, energy efficiency (EE) is one of the most pivotal metrics to evaluate the performance of WSNs, for the reason that devices usually work with limited power supply. Chen et al. ⁶ formulated the energy consumption minimisation problem as an optimisation problem in a multiple input multiple output (MIMO) multihop network and investigated the trade-off between the EE and the bandwidth efficiency. Vahid Nazari Talooki et al. ⁷ proposed a new routing protocol (E2AODVv2) to provide a weighted and flexible trade-off between energy consumption and the load dispersion.

Since devices are often deployed in open areas, WSNs could be eavesdropped easily. Jawandhiya et al. ⁸ summarised different attacks in multihop networks, which were active or passive to interrupt or wiretap information transmission. The information-theoretic security (ITS) has become a great issue^9,10,11 since Wyner’s ¹² work in 1975. It also lead Choi to investigate the optimal multipath routing scheme for the throughput maximisation under ITS constraints. ¹¹

Related work

In WSNs, sensor nodes can play different roles: the helpers which help to relay signals, the jammers which send jamming signals to interfere the transmitting, and the potential eavesdroppers which might wiretap signals. If some sensor nodes are captured by eavesdroppers, they are thought to be untrusted. The beamforming technique for physical layer security and its performance is discussed with untrusted relays in Mo et al., ¹³ Wang et al., ¹⁴ and Aggarwal and Trivedi, ¹⁵ where the relays played as both helpers and potential eavesdroppers.

Choi ¹¹ proposed a novel scene of eavesdroppers wiretapping the WSN in which there are four types of nodes: a source node (SN) transmits packets to a destination node (DN) through relay nodes (RNs). Some of RNs are captured and become eavesdroppers (ENs). The SN cannot check out the ENs since they participate in the transmission from the SN to the DN as normal RNs. In order to prevent the ENs from decoding the transmitted packets, the SN takes multipath routing to ensure the transmission security. In this condition, the binary erasure channel (BEC) model was adopted to describe channels between neighbouring nodes in Choi, ¹¹ which is also adopted in Tsirigos and Haas.^5,16

In this article, we use the same system model and the channel model as in Choi. ¹¹ Instead of aiming at the throughput maximisation, we focus on the EE maximisation of the network with the ITS constraint and the secrecy channel capacity. The contributions of this article can be summarised as follows:

1. We allocate each path with a certain probability that the SN may send information through this path. We derive the achievable channel capacity of the network based on the BEC model with respect to the allocated probabilities of all the paths. Then, we formulate the optimisation problem of the EE maximisation with the ITS constraint and find the optimal multipath routing scheme with the Charnes–Cooper transformation.

2. As the ITS constraint depends on the secrecy channel capacity of the network, the optimisation problem of the secrecy channel capacity of the network is derived. An iterative algorithm is proposed to solve the optimisation problem and find out the maximal required secrecy channel capacity.

3. Performance analysis of the ITS routing is carried out under two conditions: (1) the erasure probabilities of all the links are equivalent and (2) the erasure probabilities are independent and identically distributed (IID). Constraint conditions are derived for the ITS routing.

The organisation of this article is presented as follows. The system model and related concepts are described in section ‘System model’. In sections ‘Bit allocation scheme for maximising the EE with security constraints’ and ‘Bit allocation scheme for maximising the secrecy channel capacity’, two optimisation problems corresponding to the above two objectives are derived, and the algorithms are also proposed to find solutions. Performance analysis is studied in section ‘Performance analysis’. Section ‘Simulation results’ presents the simulation results and validates the efficiency of our proposed algorithms. Finally, we conclude the article in section ‘Conclusion’.

System model

For multipath routing in multihop WSNs, it is difficult to derive the capacity of the network from the perspective of physical layer, since the signals are transmitted through a number of intermediate nodes before they reach the destination. Thus, in this article, we use the BEC model to simplify the channels between nodes based on the following known results.

Axiom 1. Capacity of the BEC. For the BEC in Figure 1, X represents the transmit node, while Y denotes the receive node, ‘ $\epsilon$ ’ and ‘?’ denote the erasure probability and the erasure state from node X to node Y, respectively. The channel capacity of this BEC is $(1-\epsilon )$ .

Figure 1.

Binary erasure channel model.

Property 1. For a network with two links of BEC serially connected, if ${\epsilon }_1$ and ${\epsilon }_2$ denote the erasure probabilities of the links, its channel capacity is $(1-{\epsilon }_1)(1-{\epsilon }_2)$ .

Property 2. For a network where two parallel links connect a source-destination transmitting pair, the probability of the source node allocating the information to the ith link is denoted by $p_i$ , $i=1,2$ with $p_1+p_2=1$ . In addition, denote by ${\epsilon }_i$ the erasure probability of the ith link. Then, the channel capacity of the network is $p_1(1-{\epsilon }_1)+p_2(1-{\epsilon }_2)$ .

Properties 1 and 2 can be intuitively obtained according to Axiom 1. Hence, the definite procedures of the proof are omitted for simplicity and clarity.

Multihop parallel network

In this article, we consider a multihop WSN with multipaths as is illustrated in Figure 2. Each link between neighbouring nodes is modelled as a BEC, the S node (SN) is the transmit node and the D node (DN) is the receive node. In the network, the SN sends the information to the DN through K disjoint multipaths between them. Erasure probabilities of all the links are available to the SN. There is one or more smart eavesdropping nodes (ENs) which the SN cannot recognise. They behave like normal nodes and cooperate to eavesdrop the information. The SN is to distribute a message sequence along multipaths according to a certain probability distribution. The probability distribution can be modified to realise different routing schemes. Key parameters of the network are described in Table 1.

Figure 2.

Multihop parallel network with BEC channel model.

Table 1.

Parameter definition table of the multihop parallel network.

K	The number of potential paths between the SN and the DN
$L_k$	Link number of the kth path, $1\le k\le K$
m	The number of eavesdropping nodes
C	The channel capacity of the network
$C_s$	The secrecy channel capacity of the network
$C_k$	The channel capacity of the kth path
$C_e$	The channel capacity of all eavesdropping channels
$C_{\mathrm{req}}$	The minimum threshold of the secrecy channel capacity
$p_k$	The probability that the SN allocates the information to the kth path
$d_{k,l}$	The distance of the lth hop of the kth path, $1\le l\le L_k$
${\epsilon }_{k,l}$	The erasure probability of the lth hop of the kth path
${\epsilon }_k$	The erasure probability of the kth path

SN: source node; DN: destination node.

For the network in Figure 2, the capacity of the channel connecting the SN to the lth intermediate node along the kth path is ${\tilde{C}}_{k,l}=\underset{j=1}{\overset{l}{\Pi }}(1-{\epsilon }_{k,j})$ . Based on the data processing inequality, it is obvious that ${\tilde{C}}_{k,1}\ge {\tilde{C}}_{k,l}$ always satisfy. If one eavesdropper wiretaps this path, the first intermediate node is the best choice. In order to consider the worst case for secure transmissions, we could assume that eavesdroppers are at the first nodes in any paths.

Energy consumption model

As is mentioned in Chen et al. ⁶ and Talooki et al., ⁷ energy consumption is a critical issue in multihop WSNs. Measured results on devices show that consumed energy grows linearly with the number of bits transmitted. ¹⁷ In El-Moukaddem et al. ¹⁷ and Heinzelman et al., ¹⁸ the following energy consumption model was considered

$$E_T\left(d\right)=n(a+b{d}^2)$$

(1)

where $E_T\left(d\right)$ is the energy consumed by information transmission, n denotes the number of transmitted bits, d is the distance between the transmitter and receiver, and a as well as b is constant depending on the channel environment.

In this article, we also adopt this energy-consuming model in equation (1) to take the EE into account in secure multipath routing.

Bit allocation scheme for maximising the EE with security constraints

In this section, we study ITS routing with EE maximisation. The network’s EE metric can be defined as information bits transmitted per Joule, which is given by

$${\mathrm{f}}_{\mathrm{EE}}=\frac{C}{E}$$

(2)

where E and C denote the energy consumed by the source sending one symbol and the channel capacity of the network, respectively.

Channel capacity

According to Property 1, for the kth path in the network, the achievable channel capacity of the channel connecting SN to the lth intermediate node is denoted as $C_{k,l}$ , then $C_{k,1}=p_k(1-{\epsilon }_{k,1})$ , and $C_{k,2}=p_k(1-{\epsilon }_{k,1})(1-{\epsilon }_{k,2})$ . So the achievable channel capacity of the kth path $C_k$ is

$$C_k=p_k\underset{l=1}{\overset{L_k}{\Pi }}(1-{\epsilon }_{k,l})$$

(3)

and the sum channel capacity becomes

$$C(p_1,p_2,\dots ,p_K)=\sum _{k=1}^K{p}_k(1-{\epsilon }_k)$$

(4)

where ${\epsilon }_k=1-\underset{l=1}{\overset{L_k}{\Pi }}(1-{\epsilon }_{k,l})$ , which denotes the overall erasure probability of the kth path. Let $\mathbf{r}=[p_1,p_2,\dots ,p_K{]}^{\mathrm{T}}$ and $\mathbf{a}=[1-{\epsilon }_1,1-{\epsilon }_2,\dots ,1-{\epsilon }_K{]}^{\mathrm{T}}$ , then equation (4) can be transformed to

$$C\left(\mathbf{r}\right)={\mathbf{a}}^{\mathrm{T}}\mathbf{r}$$

(5)

Energy consumption

Using equation (1), the energy consumed by the kth path per unit time can be expressed as

$$\begin{array}{c}{\mathrm{E}}_k=E_{k,s}+\sum _{l=1}^{L_k-1}{E}_{k,l}\hfill \\ =p_k(a+{\mathrm{bd}}_{k,1}^2)+\sum _{l=1}^{L_k-1}{C}_{k,l}(a+{\mathrm{bd}}_{k,l+1}^2)\hfill \\ =p_k\sum _{l=0}^{L_k-1}(a+{\mathrm{bd}}_{k,l+1}^2)\underset{m=0}{\overset{l}{\Pi }}(1-{\epsilon }_{k,m})\hfill \end{array}$$

(6)

where $E_{k,s}$ denotes the energy the SN consumed to send information along the kth path, $d_{k,l+1}$ denotes the distance between nodes of the $(l+1)$ th hop along the kth path and we assume that ${\epsilon }_{k,0}=0$ .

The energy consumed by the whole network is

$$\mathrm{E}(p_1,p_2,\dots ,p_K)=\sum _{k=1}^K{\mathrm{E}}_k$$

(7)

Let ${\beta }_k=\sum _{l=0}^{L_k-1}(a+{\mathrm{bd}}_{k,l+1}^2)\underset{m=0}{\overset{l}{\Pi }}(1-{\epsilon }_{k,m})$ and $\mathbf{b}=[{\beta }_1,{\beta }_2,\dots ,{\beta }_K{]}^{\mathrm{T}}$ , equation (7) can be simplified as

$$\mathrm{E}\left(\mathbf{r}\right)=\mathrm{E}(p_1,p_2,\dots ,p_K)={\mathbf{b}}^{\mathrm{T}}\mathbf{r}$$

(8)

The ITS constraint

According to Bloch et al., ⁹ the secrecy channel capacity is defined as

$$C_s\left(\mathbf{r}\right)=\max (C\left(\mathbf{r}\right)-C_e\left(\mathbf{r}\right),0)$$

(9)

where $C_e\left(\mathbf{r}\right)$ denotes the channel capacity of all eavesdropping channels with the bit allocation scheme $\mathbf{r}$ .

In this article, the ITS constraint is defined as

$$C_s\left(\mathbf{r}\right)\ge C_{\mathrm{req}}$$

(10)

where $C_{\mathrm{req}}$ is the minimum threshold of the secrecy channel capacity and satisfies $0<C_{\mathrm{req}}<1$ . When certain bit allocation scheme satisfies equation (10), the multipath routing with that scheme is called the ITS routing.

The SN has no knowledge of how many ENs there are and where they are deployed. Since bit allocation by the SN depends on the number of ENs, the SN has to consider the worst condition. Assuming that there are m ENs ( $m<K$ ) in the network, which lie at the head nodes of different paths and collude with each other to eavesdrop messages from the SN, the derivation of eavesdropping channel capacity can be found as follows.

As derived in Choi, ¹¹ let ${\Gamma }_m$ . denote the set of the indexes of m different multipaths where the ENs can join to forward messages from the SN. Then, it follows

$${\Gamma }_m=\{(k_1,k_2,\dots ,k_m):k_p<k_q,\mathrm{for\; all}p<q\}$$

Let $M_m$ denote the element number of the set ${\Gamma }_m$ , then $M_m=\left|{\Gamma }_m\right|=\left(\begin{array}{c}K\hfill \\ \multicolumn{1}{c}{m}\end{array}\right)$ . Denote by ${\mu }^m(i)$ the ith element of ${\Gamma }_m$ and ${\mu }_j^m(i)$ the index of multipaths for the jth element of ${\mu }^m(i)$ .

If the SN knows the index set $S_{\mathrm{eav}}$ of multipaths where m eavesdroppers are deployed, then $S_{\mathrm{eav}}\in {\Gamma }_m$ . Assuming $S_{\mathrm{eav}}={\mu }^m(i)$ , the eavesdropping channel capacity is

$$C_e(p_1,p_2,\dots ,p_K)=\sum _{j=1}^m{p}_{{\mu }_j^m(i)}(1-{\epsilon }_{{\mu }_j^m(i),1})$$

In this article, we assume that the SN has no information about eavesdroppers’ deployment. Considering the worst condition, the eavesdropping channel capacity becomes

$$C_e(p_1,p_2,\dots ,p_K)=\underset{{\mu }^m(i)\in {\Gamma }_m}{\max }\sum _{j=1}^m{p}_{{\mu }_j^m(i)}(1-{\epsilon }_{{\mu }_j^m(i),1})$$

(11)

After substituting equations (4), (9) and (11) into equation (10), the ITS constraint can be rewritten as

$$\sum _{k=1}^K{p}_k(1-{\epsilon }_k)-\underset{{\mu }^m(i)\in {\Gamma }_m}{\max }\sum _{j=1}^m{p}_{{\mu }_j^m(i)}(1-{\epsilon }_{{\mu }_j^m(i),1})\ge C_{\mathrm{req}}$$

(12)

For $\forall {\mu }^m(i)\in {\Gamma }_m$ , we can intuitively find that

$$\underset{{\mu }^m(k)\in {\Gamma }_m}{\max }\sum _{j=1}^m{p}_{{\mu }_j^m(k)}(1-{\epsilon }_{{\mu }_j^m(k),1})\ge \sum _{j=1}^m{p}_{{\mu }_j^m(i)}(1-{\epsilon }_{{\mu }_j^m(i),1})$$

(13)

After substituting equation (13) into equation (12), we can obtain that for $\forall {\mu }^m(i)\in {\Gamma }_m$

$$\sum _{k=1}^K{p}_k(1-{\epsilon }_k)-\sum _{j=1}^m{p}_{{\mu }_j^m(i)}(1-{\epsilon }_{{\mu }_j^m(i),1})\ge C_{\mathrm{req}}$$

(14)

In order to simplify equation (14), we define a series of $K\times 1$ column vectors, of which the ith vector ( $1\le i\le M_m$ ) is defined as equation (15). We also define the $K\times M_m$ matrix ${\mathbf{U}}_{(m)}$ as equation (16)

$$[{\mathit{u}}_{(m),i}{]}_q=\{\begin{array}{cc}1-{\epsilon }_{{\mu }_j^m(i),1}+{\epsilon }_{{\mu }_j^m(i)}\hfill & \mathrm{if}q={\mu }_j^m(i),j=1,2,\dots ,m\hfill \\ \multicolumn{1}{c}{{\epsilon }_q}& \mathrm{otherwise}\hfill \end{array}$$

(15)

$${\mathbf{U}}_{(m)}=[{\mathit{u}}_{(m),1}{\mathit{u}}_{(m),2}\dots {\mathit{u}}_{(m),M_m}]$$

(16)

Then, (14) can be expressed as follows

$${\mathbf{U}}_{\left(m\right)}^{\mathrm{T}}\mathbf{r}⪯\mathbf{q}$$

(17)

where $\mathbf{q}$ is an $M_m\times 1$ column vector with each element being $1-C_{\mathrm{req}}$ .

Problem formulation and the optimal bit allocation scheme

By substituting equations (5) and (8) into equation (2), the EE of the multihop network can be formulated as

$$\mathrm{f}\left(\mathbf{r}\right)=\frac{{\mathbf{a}}^{\mathrm{T}}\mathbf{r}}{{\mathbf{b}}^{\mathrm{T}}\mathbf{r}}$$

(18)

We define the EE of transmission along the kth path as $e_k$ . With equations (2), (3) and (6), it is observed that

$$e_k=\frac{C_k}{E_k}=\frac{p_k(1-{\epsilon }_k)}{p_k{\beta }_k}=\frac{1-{\epsilon }_k}{{\beta }_k}$$

Without loss of generality, we assume that the EE of transmission along the first path is the largest, that is, $e_1\ge e_k$ , so $1-{\epsilon }_k\le {\beta }_k{e}_1$ . Then, equation (18) can be rewritten as

$$\begin{array}{c}\mathrm{f}\left(\mathbf{r}\right)=\frac{{\mathbf{a}}^{\mathrm{T}}\mathbf{r}}{{\mathbf{b}}^{\mathrm{T}}\mathbf{r}}\hfill \\ =\frac{\sum _k{p}_k(1-{\epsilon }_k)}{\sum _k{p}_k{\beta }_k}\hfill \\ \le \frac{e_1\sum _k{p}_k{\beta }_k}{\sum _k{p}_k{\beta }_k}\hfill \\ =e_1\hfill \end{array}$$

Clearly, the optimal EE of the network is obtained when transmitting all the information sequences along the most energy-efficient path. However, such a scheme may not satisfy the ITS constraint. Thus, the problem of maximising EE of the multihop network with the ITS constraint can be formulated as follows.

Formulation 1. Bit allocation design for maximising the network’s EE with the ITS constraint. For a given minimum threshold of the secrecy channel capacity $C_{\mathrm{req}}$ , the best bit allocation design, that is, the optimal $\mathbf{r}$ can be obtained by solving

$$\begin{array}{cc}\underset{\mathbf{r}}{\max }\hfill & \frac{{\mathbf{a}}^{\mathrm{T}}\mathbf{r}}{{\mathbf{b}}^{\mathrm{T}}\mathbf{r}}\hfill \\ \multicolumn{1}{c}{\mathrm{s}.\mathrm{t}.}& \{\begin{array}{ccc}{1}^{\mathrm{T}}\mathbf{r}\hfill & =\hfill & 1\hfill \\ \multicolumn{1}{c}{{\mathbf{U}}_{\left(m\right)}^{\mathrm{T}}\mathbf{r}}& ⪯\hfill & \mathbf{q}\hfill \\ \multicolumn{1}{c}{\mathbf{r}}& ⪰\hfill & 0\hfill \end{array}\hfill \end{array}$$

(19)

where $0$ is a $K\times 1$ zero column vector.

Problem (19) is a quasi-concave problem due to the linear fractional structure of its objective function. These kinds of problems can always be solved by a bisection methodology, ¹⁹ where the globally optimal solution is sequentially searched by solving a sequence of feasibility problems. However, in this article, we propose a more efficient method to solve it. We use the Charnes–Cooper transformation to reformulate (19) into a convex problem. Let $\mathbf{s}=\frac{\mathbf{r}}{{\mathbf{b}}^{\mathrm{T}}\mathbf{r}}$ and $t=\frac{1}{{\mathbf{b}}^{\mathrm{T}}\mathbf{r}}$ , equation (19) can be rewritten as

$$\begin{array}{cc}\arg \underset{\mathbf{s},t}{\max }\hfill & {\mathbf{a}}^{\mathrm{T}}\mathbf{s}\hfill \\ \multicolumn{1}{c}{\mathrm{s}.\mathrm{t}.}& \{\begin{array}{ccc}{1}^{\mathrm{T}}\mathbf{s}\hfill & =\hfill & t\hfill \\ \multicolumn{1}{c}{{\mathbf{U}}_{(m)}^{\mathrm{T}}\mathbf{s}}& ⪯\hfill & t\mathbf{q}\hfill \\ \multicolumn{1}{c}{\mathbf{s}}& ⪰\hfill & 0\hfill \\ \multicolumn{1}{c}{{\mathbf{b}}^{\mathrm{T}}\mathbf{s}}& =\hfill & 1\hfill \end{array}\hfill \end{array}$$

(20)

Since equation (20) is a linear problem, we can solve it by linear programming and get the optimal solution, which is denoted by $({\mathbf{s}}^{*}$ , $t^{*})$ . Hence, we come up with the following conclusion.

Conclusion 1. Solution of Formulation 1. The quasi-convex problem in Formulation 1 is equivalent to equation (20), if $({\mathbf{s}}^{*}$ , $t^{*})$ exists and is optimal. Thus, the optimal bit allocation scheme for Formulation 1 can be obtained by solving ${\mathbf{r}}_1^{*}=\frac{{\mathbf{s}}^{*}}{t^{*}}$ .

Bit allocation scheme for maximising the secrecy channel capacity

In this section, we turn our attention to the second target, that is, the bit allocation scheme for maximising the secrecy channel capacity.

According to equations (4), (9), (10) and (11), we can formulate the problem as follows.

Formulation 2. Bit allocation design for maximising the secrecy channel capacity. For the parallel multipath relay network, after defining $\mathbf{c}=[1-{\epsilon }_{1,1},1-{\epsilon }_{2,1},\dots ,1-{\epsilon }_{K,1}{]}^{\mathrm{T}}$ , ${\mathbf{V}}_{{\mu }^m\left(i\right)}=\mathrm{diag}(v_1,v_2,\dots ,v_K)$ , $v_n=\{\begin{array}{cc}1\hfill & n\in {\mu }^m\left(i\right)\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$ , the optimal bit allocation scheme $\mathbf{r}$ can be obtained by solving

$$\begin{array}{c}\underset{\mathbf{r}}{\arg \max }\underset{{\mu }^m\left(i\right)\in {\Gamma }_m}{\min }{\mathbf{a}}^{\mathrm{T}}\mathbf{r}-{\mathbf{c}}^{\mathrm{T}}{\mathbf{V}}_{{\mu }^m\left(i\right)}\mathbf{r}\hfill \\ \mathrm{s}.\mathrm{t}.\{\begin{array}{ccc}{1}^{\mathbf{T}}\mathbf{r}\hfill & =\hfill & 1\hfill \\ \multicolumn{1}{c}{\mathbf{r}}& ⪰\hfill & 0\hfill \end{array}\hfill \end{array}$$

(21)

It is obvious that the problem in equation (21) is a quasi-convex problem. According to Boyd and Vandenberghe, ¹⁹ we could use the bisection search algorithm to solve the problem. Using the bisection method, we can formulate a sub-optimisation problem with a variable parameter $\Lambda$ as follows

$$\begin{array}{cc}\underset{\mathbf{r}}{\min }\hfill & 1^{\mathbf{T}}\mathbf{r}\hfill \\ \multicolumn{1}{c}{\mathrm{s}.\mathrm{t}.}& \{\begin{array}{cccc}{\mathbf{a}}^{\mathrm{T}}\mathbf{r}-{\mathbf{c}}^{\mathrm{T}}{\mathbf{V}}_{{\mu }^m\left(i\right)}\mathbf{r}\hfill & \ge \hfill & \Lambda \hfill & ,\forall {\mu }^m\left(i\right)\in {\Gamma }_m\hfill \\ \multicolumn{1}{c}{1^{\mathbf{T}}\mathbf{r}}& \le \hfill & 1\hfill & \hfill \\ \multicolumn{1}{c}{\mathbf{r}}& ⪰\hfill & 0\hfill & \hfill \end{array}\hfill \end{array}$$

(22)

Clearly, if $\Lambda$ reaches the optimal solution, that is, ${\Lambda }_{\mathrm{opt}}$ , $1^{\mathbf{T}}\mathbf{r}=1$ must be satisfied. Otherwise, by increasing $\mathbf{r}$ , a better $\Lambda$ can be obtained, which leads to the paradox that ${\Lambda }_{\mathrm{opt}}$ is the optimal solution. Thus, the inequality constraint $1^{\mathbf{T}}\mathbf{r}\le 1$ in equation (22) is equivalent to the constraint $1^{\mathbf{T}}\mathbf{r}=1$ in equation (21).

For a given $\Lambda$ , if the problem in (22) is feasible, the optimal solution of the problem in (21), ${\Lambda }_{\mathrm{opt}}$ , satisfies ${\Lambda }_{\mathrm{opt}}\ge \Lambda$ , otherwise ${\Lambda }_{\mathrm{opt}}<\Lambda$ . A description of the iterative algorithm is shown in Algorithm 1. We have the following results.

Algorithm 1. Iterative algorithm for maximising the secrecy channel capacity.
Input: Initialise the lower bound and the upper bound of $\Lambda$ , that is, ${\Lambda }_{\mathrm{lb}}$ and ${\Lambda }_{\mathrm{ub}}$ , the solution accuracy $\eta$ .
Output: The $\eta$ -optimal ${\Lambda }_{\mathrm{opt}}$ , and the $\eta$ -optimal bit allocation scheme ${\mathbf{r}}_2^{*}$
1: while ${\Lambda }_{\mathrm{ub}}-{\Lambda }_{\mathrm{lb}}>\eta$ do
2:  $\Lambda =\frac{{\Lambda }_{\mathrm{ub}}+{\Lambda }_{\mathrm{lb}}}{2}$
3: Solve the optimisation problem (22), if it is feasible, get the solution ${\mathbf{r}}_{\mathrm{opt}}$
4: if Problem (22) is feasible then
5:   ${\Lambda }_{\mathrm{lb}}=\Lambda$
6:   ${\mathbf{r}}_2^{*}={\mathbf{r}}_{\mathrm{opt}}$
7: else
8:   ${\Lambda }_{\mathrm{ub}}=\Lambda$
9: end if
10: end while
11: ${\Lambda }_{\mathrm{opt}}={\Lambda }_{\mathrm{lb}}$
12: return ${\Lambda }_{\mathrm{opt}}$ , ${\mathbf{r}}_2^{*}$

Conclusion 2. Solution of Formulation 2. For a given solution accuracy $\eta$ , the quasi-convex problem in Formulation 2 can be solved by Algorithm 1, and the outputs ${\mathbf{r}}_2^{*}$ and ${\Lambda }_{\mathrm{opt}}$ are the $\eta$ -optimal bit allocation scheme and secrecy channel capacity for Formulation 2, respectively.

Performance analysis

Since the solution to Formulation 1 does not always exist, it is important to know the probability that there exists a feasible bit allocation scheme according to Formulation 1. In this section, we analyse the impact of different parameters on this probability. It is noteworthy that analytical results in this section are generalised ones of those in Choi. ¹¹ In particular, since the ITS constraints are $C_s\ge C_{\mathrm{req}}$ and $0<C_{\mathrm{req}}<1$ , while these constraints in Choi ¹¹ are $C_s\ge C_{\mathrm{req}}$ and $C_{\mathrm{req}}=0$ , generalised results are obtained in this section.

Unfortunately, there are too many parameters to obtain simple and intuitive analysis for the above problem. Thus, we consider the following symmetric assumptions for tractable analysis:

• (A1) Assume that the erasure events of wireless links are independent of each other. The erasure probability is the same and denoted by $\epsilon$ .

• (A2) Assume that $L_k=L$ for $k=1,2,\dots ,K$ .

• (A3) Assume that the distances of wireless links are identical.

Under (A1), (A2) and (A3), it is obvious that ${\epsilon }_k$ for each k is identical, which is also true for ${\beta }_k$ . Thus, the EE of each path is identical, that is

$$e_k=e,k=1,2,\dots ,K$$

As a result, the ITS constraint for one EN (i.e. $m=1$ ) degrades to

$${(1-\epsilon )}^L-\underset{k}{\max }{p}_k(1-\epsilon )\ge C_{\mathrm{req}}$$

Formulation 1 can be reformulated as

$$\begin{array}{cc}\underset{\mathbf{r}}{\max }\hfill & e\hfill \\ \multicolumn{1}{c}{\mathrm{s}.\mathrm{t}.}& \{\begin{array}{ccc}{1}^{\mathrm{T}}\mathbf{r}\hfill & =\hfill & 1\hfill \\ \multicolumn{1}{c}{{(1-\epsilon )}^L-\underset{k}{\max }{p}_k(1-\epsilon )}& \ge \hfill & C_{\mathrm{req}}\hfill \\ \multicolumn{1}{c}{\mathbf{r}}& ⪰\hfill & 0\hfill \end{array}\hfill \end{array}$$

(23)

Theorem 1. Under the assumptions (A1), (A2), (A3) and one EN exists, the multipath routing with equal bit allocation scheme (i.e. $p_k=\frac{1}{K},k=1,2,\dots ,K$ ) would be the optimal solution when the following condition is satisfied

$$K\ge \frac{1-\epsilon }{{(1-\epsilon )}^L-C_{\mathrm{req}}}>0,\mathrm{for}0\le \epsilon <1$$

(24)

The proof procedure is shown in Appendix 1.

This result can be directly generalised to the situation with multiple ENs.

Lemma 1. Under the assumptions (A1), (A2), (A3) and m ENs exist, the equal bit allocation scheme would be the optimal solution when the following condition is satisfied

$${(1-\epsilon )}^L-\frac{m(1-\epsilon )}{K}\ge C_{\mathrm{req}}$$

(25)

The proof is omitted here for simplicity.

When $C_{\mathrm{req}}$ satisfies $C_{\mathrm{req}}<{(1-\epsilon )}^L$ , equation (25) can be rewritten as

$$K\ge \frac{m(1-\epsilon )}{{(1-\epsilon )}^L-C_{\mathrm{req}}}$$

This implies that in order to guarantee the ITS constraint, the number of multipaths, K, should grow linearly with m increasing when $\epsilon$ and L are fixed. Under the condition of ${(1-\epsilon )}^L>C_{\mathrm{req}}$ , K should grow exponentially with L for fixed m and $\epsilon$ .

Until now, we have discussed the bit allocation schemes for multipath routing when the erasure probabilities are known to the SN. However, we cannot find the optimal bit allocation scheme as shown in Conclusion 1 if the erasure probabilities are unknown. In this case, with a suboptimal bit allocation scheme, the equal bit allocation scheme, we are interested in finding the probability that the equal bit allocation scheme satisfies the ITS constraint. We have the following assumption.

(A1’) Assume that the erasure probability of each wireless link, ${\epsilon }_{k,l}$ , is IID. Let $\overline{{\epsilon }_{k,l}}$ and $\overline{{\epsilon }_k}$ be the means of ${\epsilon }_{k,l}$ and ${\epsilon }_k$ , respectively. For any k, we have $\overline{{\epsilon }_k}=1-\underset{l=1}{\overset{L_k}{\Pi }}(1-\overline{{\epsilon }_{k,l}})$ .

We consider the situation that there is one EN (i.e. $m=1$ ) for further analysis. We adopt the techniques which are also used in the proof of Theorem 2 of Choi. ¹¹ It is noted that since $C_{\mathrm{req}}$ is always positive, there are some more constraint conditions during the proof compared with Choi. ¹¹ Let ${\alpha }_{K,L}\left(\mathbf{r}\right)$ denote the probability that there is no ITS routing with K multipaths and L wireless links per each multipath.

With a single EN, it is observed that

$${\alpha }_{K,L}\left(\mathbf{r}\right)=\mathrm{P}(\sum _{k=1}^K{p}_k(1-{\epsilon }_k)-\underset{k}{\max }{p}_k(1-{\epsilon }_{k,1})<C_{\mathrm{req}})$$

After giving the definition that

$$\overline{{\alpha }_{K,L}}:=\underset{\mathbf{r}}{\min }{\alpha }_{K,L}\left(\mathbf{r}\right)$$

we have the following upper bound on $\overline{{\alpha }_{K,L}}$ , since the equal bit allocation scheme is suboptimal

$$\overline{{\alpha }_{K,L}}\le \overline{{\alpha }_{K,L}^{\left(\mathrm{eq}\right)}}=\mathrm{P}(\frac{1}{K}\sum _{k=1}^K(1-{\epsilon }_k)<\frac{\underset{k}{\max }(1-{\epsilon }_{k,1})}{K}+C_{\mathrm{req}})$$

(26)

Theorem 2. Under the assumptions (A1’), (A2), (A3) and one EN exists, for a fixed and finite L, it can be observed that $\mathrm{E}\left({\epsilon }_k\right)=\overline{{\epsilon }_k}=\overline{\epsilon }$ for any k, when $1-\overline{\epsilon }\ge C_{\mathrm{req}}$ , we have

$$\underset{K\to \infty }{\lim }\overline{{\alpha }_{K,L}}=0$$

(27)

The proof procedure is provided in Appendix 1.

Simulation results

In this section, we present some simulation results. We assume that the number of links per path is the same, denoted by L, and the distance of any neighbouring nodes is equal to 100 m. In the energy consumption model, we let $a=0.6\times {10}^{-7}\mathrm{J}/\mathrm{bit}$ , $b=4\times {10}^{-10}\mathrm{J}{\mathrm{m}}^{-2}/\mathrm{bit}$ , ¹⁷ ${\epsilon }_{k,i}(k=1,2,\dots ,K;i=1,2,\dots ,L_k)$ is IID and assume that the following uniform distribution with ${\epsilon }_{\max }=0.1$ always satisfy

$$\mathrm{P}\left({\epsilon }_{k,i}\right)=\{\begin{array}{cc}\frac{1}{{\epsilon }_{\max }}\hfill & 0<{\epsilon }_{k,i}<{\epsilon }_{\max }\hfill \\ \multicolumn{1}{c}{0}& \mathrm{otherwise}\hfill \end{array}$$

(28)

For comparison, we also consider three different schemes: the optimal energy-efficient single-path routing, the ITS routing and multipath routing with the equal bit allocation scheme. Formulation 1 shows that the ITS constraint is not always feasible. In our simulation, when there is no ITS bit allocation scheme for Formulation 1, the equal bit allocation scheme is adopted. According to the randomness of the erasure probabilities, 1000 times of simulations for each situation are carried out to find the performance of different schemes.

In general, when the number of multipaths increases, the EE of the network using the first scheme could increase and this gain is called multiroute path selection (MRPS) diversity gain. ²⁰ The first scheme is also called the MRPS routing. Although the ITS routing cannot reach the optimal EE of the network with the MRPS routing, it is more secure in the presence of eavesdroppers.

Figure 3 shows the EE of the network and the secrecy channel capacity for the number of multipaths, when $L=4$ and $m=1$ . Clearly, as K increases, the secrecy channel capacity grows and the EE of the network for the MRPS routing and the optimal ITS routing improves. This results from the fact that it becomes easier to find the optimal paths with a large K. The EE of the network decreases when $C_{\mathrm{req}}$ increases because it becomes harder and harder to find the optimal ITS routing scheme while $C_{\mathrm{r}\mathrm{eq}}$ is enlarged.

Figure 3.

Energy efficiency and secrecy channel capacity of various schemes ( $L=4,m=1$ ).

Figure 4 shows the impact of L on the EE and the secrecy channel capacity, when $K=4$ and $m=1$ . For a fixed K, paths become less efficient and reliable when L increases. From Figure 4 we can observe that the EE of the network and the secrecy channel capacity both decrease with L. When $L=10$ , the maximal secrecy channel capacity is lower than 0.4, it is impossible to find the optimal ITS routing with $C_{\mathrm{req}}=0.4$ . At this time, the optimal ITS routing degrades to the multipath routing with equal bit allocation scheme as mentioned above.

Figure 4.

Energy efficiency and secrecy channel capacity of various schemes ( $K=4,m=1$ ).

Figure 5 shows the EE and the secrecy channel capacity for various numbers of cooperative ENs, m, when $K=10$ and $L=4$ . Without the ITS constraint, the EE for the MRPS routing and the multipath routing with equal bit allocation scheme should remain stable with the growth of m. The secrecy channel capacity diminishes with m, while the three optimal ITS routing schemes with different $C_{\mathrm{req}}$ become the equal bit allocation scheme one after another.

Figure 5.

Energy efficiency and secrecy channel capacity of various schemes ( $K=10,L=4$ ).

It is clear that the probability of existing ITS routing increases when K increases for a fixed L and $m=1$ according to Theorem 2. In Figure 6, with the distribution of ${\epsilon }_{k,l}$ in equation (28), $L=10$ and $m=1$ , thus $1-\overline{\epsilon }\approx 0.6$ . When $C_{\mathrm{req}}<1-\overline{\epsilon }$ (e.g. $C_{\mathrm{req}}=0.1,0.2,0.4,0.5$ ), the probability of successful ITS routing approaches to 1 with the increase in K. However, when $C_{\mathrm{req}}>1-\overline{\epsilon }$ (i.e. $C_{\mathrm{req}}=0.8$ ), it is impossible for ITS routing. That coincides with the result of Theorem 2.

Figure 6.

Probability of successful ITS bit allocation ( $L=10,m=1$ ).

Conclusion

In this article, we focus on multipath routing for the EE and secrecy channel capacity of WSNs. Based on the BEC model, we transform the problem of designing routing with the ITS constraint into that of bit allocation to multipaths. The problem of maximising the EE of the network with the ITS constraint is formulated and solved with the Charnes–Cooper transformation. The problem of maximising the secrecy channel capacity has been formulated and an iterative algorithm is proposed. The performance analysis is carried out with the constraint of multiple parameters (the number of multipaths, the number of links per path and so on) to the ITS routing. It is shown that as there are more multipaths participating into the transmission, the probability of the ITS routing increases and the transmission becomes more secure. Simulations also verify the results that the ITS routing is more secure, while the EE of the network with ITS routing is lower than that with MRPS routing.