Network Coding for Wireless Sensor Network Cluster over Rayleigh Fading Channel: Finite State Markov Chain

Show more

1. Introduction

Network Coding (NC) [1] is a novel technique originally proposed for multicasting information over wireline networks of noiseless channels. It is based on combining received information packets; that is, each intermediate NC node computes a certain encoding function of the received packets and forwards the resulting packet towards its destination.

In [2] [3] , NC is applied over WSN cluster that communicates through a base station over Additive White Gaussian Noise (AWGN) channel resulting in saving in the transmission number of Automatic Repeat Request and hence the saving in the transmission power, unlike the work which is proposed in this paper where NC is propped to be applied over fading [4] . In [3] , physical layer NC has been applied in a practical manner over Full Duplex system, however, the NC is applied in this paper in a random combination, which is unlike the proposed work where NC is applied in a deterministic manner. States that the relay can “handle” multiple streams by using either time sharing or sending combined information, in fact, in our multiple stream NC technique, our key idea is to find a well organized marriage between these two techniques, so, we first find out the proper combine, and then use time sharing principle to broadcast, which is totally unlike the strong potentials of NC in wireless packet networks, recently pointed out in [5] [6] [7] and references therein. The data streams are encoded, and protected using a robust error control code, and then modulated, before transmission over wireless channels. In [4] , full duplex channel model with two senders, two receivers, and one relay was studied. Paper [8] proposes a new coding algorithm that makes use of feedback to dynamically adapt the code (three-receiver case).

The rest of the paper is organized as following: Section 2 illustrates the system model, while Section 3 introduces WSN protocol based on network coding. Section 4 shows the simulation results and the experiment conditions where the results collected. Finally, Section 6 concludes the paper.

2. System Model

We consider a WSN (or its cluster) that consists of M ≥ 2 nodes M_{1}, M_{2}, ∙∙∙, M_{M} that transmit equal-length information packets to a common destination node D. The nodes can hear one another as the transmission of different nodes is scheduled over non-overlapping time intervals. For example, users may be co- coordinately scheduled in TDMA fashion by the cluster-head D. We assume that the wireless channel between any two nodes can be modelled as a Rayleigh block- fading channel, where the instantaneous SNR is assumed to be constant during a single packet transmission period. Between packet transmissions, we assume that the channel changes its state according to a finite-state packet level Markov chain (FSMC) model described in [9] . An example of the system model is illustrated in Figure 1, where M = 8 sensor nodes are placed circularly around the cluster-head D. We use the circular placement model in the following without loss of generality; any configuration of sensor nodes can be analyzed in a similar way as the (Rayleigh fading) channel behaviour (i.e. the average received SNR) depends only on the distance between communicating nodes.

We have chosen this design to obtain different distances between users and then apply FSMC according to the unequal distance. Extensions to more complex transmission schemes that include error-correction coding and/or different

Figure 1. WSN example with M = 8 nodes, M_{i} and destination D, M_{1} is chosen to show all distances.

modulation alphabets can be easily included as they will only affect packet loss probabilities on Rayleigh block-fading links. The destination informs the nodes with a simple broadcast feedback message when it successfully decodes all M messages. We assume that this feedback message is always reliably transmitted. In the first stage, each node N_{i} broadcasts its own packet in the corresponding time slot. Each of the remaining nodes in the cluster, that includes the remaining M − 1 user nodes and the destination node D, receives the packet. The probability of correct packet reception at any of the receiving nodes depends on the instantaneous channel conditions (i.e. the state of the FSMC model) of the corresponding wireless channel, which, on a large scale, depends on the distance between communicating nodes. Stage 1 ends after M time slots.

In the second transmission stage, we propose different random or deterministic combination strategies with their relative merits and disadvantages as discussed in the following subsections. Our proposed combination strategies can be seen as a simple NC operation over binary field. Indeed, as in NC, a node computes a linear combination of incoming packets.

Baseline Non-Cooperative Strategy

For the circular symmetric scenario where users are on the same distance from D, p does not change for different users and can be calculated by averaging the probabilities of packet loss over the states of the corresponding FSMC channel model.

More precisely, for the packet level FSMC model containing K states described by the set of steady state probabilities $\pi =\left\{{\pi}_{1},{\pi}_{3},\cdots ,{\pi}_{K}\right\}$ , and the set of packet error probabilities ${P}_{e}=\left\{{p}_{1},{p}_{3},\cdots ,{p}_{\pi}\right\}$ for uncoded BPSK transmission [9] , the average packet loss probability $p=\pi {P}_{e}^{T}$ . We will use this performance prediction as a baseline for comparison with the cooperative schemes we describe in the next section.

3. WSN Protocol Based on Network Coding

In this section, we heuristically introduce several network coded cooperation strategies in the same way we proposed protocols over the erasure channel, and in the next section, we evaluate their performance in a realistic simulation setting. Before proceeding, we introduce several notions we will use for description of our cooperative protocols. The next neighbour of the node N_{i} is the node M_{i}_{+ 1}, with an exception of the node M_{M} whose next neighbour is M_{1}. Similarly, we define the previous neighbour of a node. We assume that node indexing is done during the cluster formation and is coordinated by the cluster head node D. The nearest received neighbour of the node N_{i} is the node or set of which are closest in terms of distance from M_{i} and from which the node M_{i} has correctly received a packet in the previous transmission stage. We assume that a node can use Received Signal Strength Indicator (RSSI) to determine the set of nearest received neighbours.

In a similar way, we define the farthest received neighbour or the set of farthest received neighbours (if there is more than one). The packet header is additional and usually very small information content appended to encoded packet to signal certain additional information about cooperative behaviour from each user to the destination node D. For each cooperation strategy, we assume that the header content is defined in advance as part of the protocol definition, and is known by both the user nodes and the destination node D.

3.1. Next/Previous Neighbour Combining

The proposed cooperative strategies differ only by the node behaviour during the second stage transmission; the first stage assumes selfish transmission by all the user nodes. For this strategy, if the node fails to receive any of the next or previous node’s packets after the first stage, it retransmits its own packet (i.e. remains in the selfish mode). If the node receives either the next or the previous node’s packet, it combines the received packet with its own and broadcasts the encoded packet during the second stage. If the node receives both the next and the previous user’s packet, it combines all three packets as shown in Equation (1)

${C}_{r\left(i\right)}={\displaystyle \underset{j=1-1}{\overset{i+1}{\sum}}{X}_{j}}$ (1)

where
${C}_{r\left(i\right)}$ is the combined transmitted packet at M_{i}, and X_{j} = 0 if the user M_{i} does not decode the packet sent from the user M_{j}. Two-bit binary header field is sufficient for the node to signal the destination which of the four possible second stage behaviour it has applied.

3.2. Nearest/Farthest Neighbour Combining

In this strategy, the node inspects the set of received packets after the first stage. If none of the packets is overheard, the node remains in the selfish mode during the second stage. If the set of received packets is non-empty, the node combines its own packet with the packet received from the nearest (farthest) user. If more than one of nearest (farthest) user’s packet is received, one of the nearest (farthest) users is randomly selected. The motivation for the farthest user selection is that it should increase the diversity of created equations, as the farther the nodes are, the less is the probability they will overhear each other’s packets. The second phase transmission requires log2_{M}-bits header field to explicitly identify the node whose packet is included in the second stage combination; if the node remains selfish, it can simply signal its own log2_{M}-bit identifier (each of M nodes can be uniquely identified by log2_{M}-bit identifier).

3.3. All Received Packets Combining

In this strategy, the node combines all the packets received after the first stage and broadcast the combined packet during the second stage. Unlike the nearest/ farthest strategy, where up to two information packets are combined in the second stage by each node, in this strategy, the node may combine any number of up to M information packets during the second stage.

To describe the encoded combination transmitted in the encoded packet, the node appends M-bit header field in which the i-th bit is set to one if the information packet created by the node M_{i} is included in the encoded packet.

4. Simulation Set-Up and Results for Rayleigh Fading Channel

Consider N users arranged around a circle with radius R from the destination and where the angular separation between users is π/M radians as shown in figure 1, where FSMC represents the Rayleigh Fading Channel.

The algorithm works from the transmission values, which is assumed to be the same for all users at all stages. This P_{T} power is transmitted to the M users and D, to be received as
${P}_{R}\left(R\right)$ . The path losses is calculation reflects the distance Matrix, i.e. the received SNR Matrix is related just to the distance as the transmitted power is assumed to be the same for all users.

The first element of the SNR R_{r}_{(}_{1, 1)} received Matrix represents the received SNR value from user one to D, and R_{r}_{(2, 2)} represent the second user to D and so on.

The FSMC needs just the number of the state-space and the received SNR partition values to represents the channel quality BER at the time, and to determine the future state, taking into consideration that the probability and future states Matrix’s diagonal represents the M users to D transmission [9] .

At the end of the stage, we evaluate the received packets, and in the case of all packets received, the algorithm ends by sending the future states to the FSMC for the new transmission, and an acknowledgement message sent from D to the M users confirming the end of the algorithm, otherwise, the next stage follows, where users apply NC over the overheard packets between them and re-transmit the combined packets.

As the added part of the combined packets is neglect able, we assume that the same power transmission for the combined packet.

At the same time, the future states Matrix is fed to FSMC to be the next current state which used to determine the new future state-spaces for the transmission after the next.

5. Simulation Results

In this section, we present simulation results for the proposed node cooperation schemes based on NC introduced in the previous section. We focus on a realistic modeling of a circular cluster WSN topology with M = 8 user nodes and the destination node D, as presented in Figure 1. The radius of the circle, i.e., the distance between the user nodes and the destination node D is r = 25 m. The users are regularly placed on a circle with an angular distance between the neighbouring nodes equal $\alpha =2\pi /M=\pi /4$ rad.

The carrier frequency f_{c} = 2.4 GHz. The nodes transmit information/encoded packets using uncoded BPSK signaling where the transmission rate is set to R = 100 kbit/s and the bandwidth of the transmitted signal is BW = 50 kHz. The equal length information/encoded packets are of size L = 500 bits, which makes the duration of a single packet transmission equal T_{p} = L/R = 5 ms. The power of MICAz nodes is changed from P_{T} = −15 dBi to P_{T} = 5 dBi with the step of 5 dBi. The gain of both transmit and receiving antennas is assumed to be G_{T} = G_{R} = 5 dBi. The path loss between sensor motes follows the well-known Friis path-loss law [10] :

${P}_{R}\left(R\right)={G}_{T}{G}_{R}\cdot {\left(\lambda /4\pi \right)}^{2}{\left(1/R\right)}^{n}\cdot {P}_{T}$ , (2)

where $\lambda =c/f$ is the carrier wavelength and the path-loss exponent which is set to n = 4.4 [11] .

Taking into consideration that unlike [12] where the partially blind instantly decodable network codes for lossy feedback environment its tested; in this work we use direct transmission and the these packets are not coded.

In the WSN cluster configuration, all nodes are considered to be static, which is why, once the motes are fixed, the channel gains could be considered time- invariant. However, as we are mainly interested in outdoor WSN applications, to realistically model the channel behavious, we assume very slow fading process on each of the channels between motes as a consequence of the motion of surrounding objects. We model these changes by a packet-level FSMC channel model based on the equal average duration channel state modeling [9] .

The average duration the channel spends in any FSMC state is set to C_{k} = 15 packets and the product that characterizes the fading speed of the channel relative to the packet length is set to f_{D}T_{P} = 0.01 [9] .

As the distance, transmission power and the number of users are the most important parameters in WSN design, we have investigated the protocol’s behaviour of increasing one parameter while the other two parameters are remain fixed.

Figure 2 shows how increasing the transmission power in two stages transmission improves PER significantly, moreover, it shows how our proposed strategies outperform the selfish strategy when NC is not applied, in fact, and it does outperform even the random combined strategy.

So, at PowTx = −9 dBi, PER in the selfish is as low as 0.5, compared to 0.0033, 0.0037 and 0.18 for all received combine, next neighbour only combine and random combine protocol respectively. In Figure 3, we fix PowTx at −9 dBm

Figure 2. Three stages network coding strategies for different values of PowTx at r = 25 and M = 8 compared to the selfish strategy.

Figure 3. Two stages transmission for M = 6, 8, 10, 12 and 14 for the proposed strategies at r = 25 and PowTx = −9 dBm.

and r at 25 meters, which gives best average results, and then the number of users M increased from 6 to 14.

We can notice that increasing the number of users has limited reverse reflect over the results, which is clearly justified by the fact that the path losses depends on the distance, however, there is PER noticeable losses when we increased the number of users from 6 to 14 in all received combine protocol and selfish mode, for example, increase M from 6 to 14 results to decreasing PER from 0.0008 to 0.0036 in all received combined protocol.

Notice that these results are collected under FSMC channel, which is unlike [13] where just lossy channel is assumed, which makes these results to be more practical and applicable.

The most important factor in WSN is the distance when fixing the transmission power, as the path losses law has a reverse relation to the power value of the distance as in Equation (2). Which is the reason why PER decreases from 1e^{−}^{4} to 0.59 in all received combined strategy when just increasing the transmission distance from 23 to 30 Meters at M = 8 and PowTx = −9 dBm.

Moreover, the severe PER decreasing versus the distance is justified by not applying any channel coding in our results, as shown in Figure 4.

Figure 5 shows that the next neighbour is the most combined packet in combined all packets protocol, and then the nearest. User 5 for example always receives packets from its immediate neighbours, users 4 and 6, and combines them before forwarding to D.

Figure 4. Two stages NC strategies for different values of r at M = 8 and PowTx = −9 dBm.

Figure 5. Probability of receiving packets from the node i ± n, n = 1, 2, 3 and 4, for 10,000 transmission times.

However, the rate of reception and combination of packets drops to about 26% from neighbours 3 and 7, 4% from neighbours 2 and 8, and 2.17% from its furthest neighbour (user 9). These results show why the “next user” protocol is as good as the “combine all” protocol, as most of the combined packets in the combine all protocol are the next users.

From the example of user 5, we conclude that each user gives the combination priority to its immediate neighbour. All users exhibit similar performance since the model generating the outage probability is only a function of distance (when P_{T} is fixed) and all users are currently arranged in a circular fashion. However, we can generalize the distance to be the key factor in determining outage probability and hence performance for any topology of users. We also observe variability in rate of packet reception (and hence combination) for the immediate neighbour (next and previous), though they are located at the same distance from the receiving user, such as in user 5, where the reception rate for user 7 is 26% but that of user 3 is 31%. This is the result of the variability of the model justified by the changes in the FSMC state-space behaviour, which reflects the BER quality for the channel at the transmission time.

6. Conclusions

This paper proposed applying Network Coding (NC) over Wireless Sensor Network (WSN) to evaluate the benefits that can be obtained by exploiting the advantages of the NC.

The proposed scenario showed how NC saves in power consumption and bandwidth for the system, and the effect of changing the transmission distance.

Finite-State Markov Chain (FSMC) over the packet level has been implemented to obtain most practical channel for the fading Rayleigh channel, and hence the results have been shown to proof that the proposed NC technique is applicable and does meet the promise to save the transmission power and bandwidth.

In future work, we are planning to design new protocols that provide more power efficiency such as half-stage transmission protocols and collect new results for different number of sensors network and larger distances between these sensors.

Moreover, applying NC over AWGN with new protocols is regarded as important direction because it gives clearer theoretical understanding for the proposed protocols compared with Rayleigh Fading Channel.

References

[1] Ahlswede, R., Cai, N., Li, S.-Y.R. and Yeung, R.W. (2000) Network Information Flow. IEEE Transactions on Information Theory, 46, 1204-1216.

https://doi.org/10.1109/18.850663

[2] Attar, H., Stankovic, L. and Stankovic, V. (2012) Cooperative Network-Coding System for Wireless Sensor Networks. IET Communications, 6, 344-352.

[3] Tedik, S. and Kurt, G.K. (2014) Practical Full Duplex Physical Layer Network Coding. 2014 IEEE 79th VTC Spring, Seoul, Korea, May 2014.

[4] Katti, S., Katabi, I.M.D., Goldsmith, A. and Medard, M. (2007) Joint Relaying and Network Coding in Wireless Networks. ISIT, France.

[5] Shang, S.L. (2010) Applying Physical-Layer Network Coding in Wireless Networks. EURASIP Journal in Wireless Communications and Network, 2010, Article No. 1.

[6] Ning, Z.L., Okamura, K. and Li, C.M. (2013) A Joint Network Coding and Scheduling Algorithm in Wireless Networks. Proceedings of the Asia-Pacific Advanced Network, 36, 49-56.

https://doi.org/10.7125/APAN.36.7

[7] Liew, S.C., Lu, L. and Zhang, S.L. (2015) A Primer on Physical Layer Network Coding. Synthesis Lectures on Communication Network, 218 p.

[8] Douik, A., Sorour, S., Al-Naffouri, T.Y. and Alouini, M.-S. (2015) Delay Reduction for Instantly Decodable Network Coding in Persistent Channels with Feedback Imperfections. IEEE Transactions on Wireless Communications, 14, 5956.

[9] Fagoonee, L., Honary, B. and Williams, C. (2002) PUMbased Turbo Codes, Advanced Digital Signal Processing for Communication Systems. Kluwer Academic Publishers Group, Dordrecht, The Netherlands.

[10] Rappaport, T. (2001) Wireless Communications. Prentice Hall, Upper Saddle River, NJ.

[11] Puccinelli, D. and Haenggi, M. (2006) Multipath Fading in Wireless Sensor Networks: Measurements and Interpretation. Proceedings of the 2006 International Conference on Wireless Communications and Mobile Computing, Vancouver, Canada, 3-6 July 2006, 1039-1044.

https://doi.org/10.1145/1143549.1143757

[12] Sorour, S., Douik, A., Valaee, S., Al-Naffouri, T. and Alouini, M. (2014) Partially Blind Instantly Decodable Network Codes for Lossy Feedback Environment. IEEE Transactions on Wireless Communications, 13, 4871-4883.

https://doi.org/10.1109/TWC.2014.2321397

[13] El-Hihi1, M., Attar, H., Solyman, A.A.A. and Stankovic, L. (2016) Network Coding Cooperation Performance Analysis in Wireless Network over a Lossy Channel, M Users and a Destination Scenario. Communications and Network, 8, 257-280.