Chain routing algorithm of wireless sensor network based on adaptive back-off adjusted medium access control

Abstract

In order to effectively improve the data transmission efficiency of wireless sensor networks (WSN), a new wireless sensor network chain routing algorithm is proposed based on adaptive backoff-adjusted medium access control. At first, the optimal transmission back-off time of undetermined frames is estimated by the number of active nodes in this algorithm, and the performance evaluation index of WSN is presented with area coverage, transmission distance and residual energy. At the same time, the number of collisions and transmission attempt rate are given with adaptive backoff-adjusted medium access control, and the chain routing algorithm is build. Finally, the key factors influencing the algorithm are deeply studied through experimental platform and numerical simulation with MATLAB. The results show that, compared with the traditional chain routing algorithm and progressive best backoff algorithm, the algorithm has great advantages in terms of chaining efficiency, node life cycle and delay.

Keywords

Wireless sensor network chain routing energy chaining life cycle

1 Introduction

Wireless sensor networks (WSN) are sophisticated systems combining data collection, data processing, data transmission. For practical applications of WSN, power source energy and the monitoring environment are key factors for the nodes. Extension of WSN life cycles based on synergy of multiple nodes and balanced energy consumption is a key topic in this field.

The WSN routing can be categorized as flat routing protocols (density-based routing and chain routing) and hierarchical routing protocols based on their topological structures [1 –4]. The flat routing protocols are limited by low efficiency and high energy consumption (node interactions during routing, including data sending and acceptance). The RPB (rotation and PEGASIS-based protocol) WSN chain routing protocol exhibits reduced node energy consumption and homogeneous node distribution even at failures of over half sensor nodes [5]. The density-based routing (DBR) algorithm describes available energy in local areas based on the energy dependence of adjacent nodes and investigates routing energy reduction based on potential energy [6]. The D-S evidence theory based chain routing algorithm consists of chaining, selection of firs-in-chain node, and data transmission [7]. As topological reconstructions occur only in cases of node failures, unbalanced loads in clustered structures are relieved. Additionally, the structure is relatively simple and the probabilities of information channel competitions and collisions are relatively low.

The high energy consumptions in hierarchical routing protocols can be attributed to communications between cluster heads and base stations. Hierarchical WSN can achieve balanced allocations of resources and exhibits advantages in topological structure management, energy utilization, and data fusion. Nevertheless, hierarchical WSN is limited by its dynamic maintenance after topology construction. Therefore, the node address allocation mechanism in current hierarchical routing mechanisms was adjusted [8]. Specifically, a prime dynamic routing protocol was proposed. Owing to the uniqueness of primes, node locations can be clearly labeled and dynamically modified. Based on the ring based multi-hop clustered routing algorithm RB-MC, a MCBMC algorithm was proposed. The MCBMC algorithm can effectively reduce average node energy consumption and increases short life cycles of WSN [9]. Hierarchical routing protocols (EBCLQ) based on efficiency and energy consumption of communications between nodes was proposed [10]. The efficiency and energy consumption of communications between nodes are affected by the quality of chain routes and optimization of this protocol was achieved in network initialization, clustering, and data transmission. Simulations demonstrated good effectiveness and homogeneity. Based on the LEACH protocol, a cluster-chain based low energy consumption hierarchical routing protocol was proposed [11]. In this protocol, loads on the cluster head are reduced as the quantity of active nodes in the cluster is reduced, and chain communications are introduced to the cluster head. Aimed at 3D hole issues in WSN routing algorithms, a 3D cellular space system and 3D-CSR algorithm were proposed [12]. Mechanisms of cell routing were increased to exclude 3D holes and enhance efficiency and applicability of routing algorithms. GSA-based routing algorithms and life cycle based clustered algorithms were proposed [13]. The differences in cluster head node energy consumption were optimized using GSA algorithms to relieve non-uniform energy consumptions in heterogeneous WSN. In another case, the RSSI mechanism was introduced during the establishment of routing mechanism to provide node location information and achieves separation of the re-transmission authority and the decision-making authority of nodes on data packets, thus simplifying the routing process and reducing energy consumption [14]. To eliminate drawbacks of LEPS such as poor hierarchy, complicated chain evaluation, and exclusion of node energy, a novel routing algorithm EALB based on energy awareness and corresponding energy saving mechanisms was proposed [15]. This algorithm achieved reduced energy consumption and extended network life cycle.

In this study, a novel chain routing algorithm of wireless sensor for data transmission efficiency of WSN is proposed. In this algorithm, WSN performance indices are proposed and a chain routing algorithm is established based on adaptive back-off adjusted medium access control [16, 17]. Additionally, key factors affecting the proposed algorithm were investigated using numerical simulations.

This article consists of five sections: the first section introduces background, previous studies, and the proposed study, the second section discusses key performance indices of WSN routing, the third section proposes the chain routing algorithm, the fourth section describes simulations, and the fifth section gives a conclusion.

2 Performance indices

The chain routing protocol (PEGASIS) consists of chaining, selection of firs-in-chain node, and data transmission. The network was initialized at the chaining stage: the node closest to the sink was selected as the tip node, identify the node closest to the tip node (denoted as Node a), identify the chain node closest to Node a (denoted as Node b) and defined as the precursor node of Node a. Node a and b are connected and Node a was added into the chain. If all nodes have been added into the chain, chaining is completed; otherwise repeat the procedures above.

Selection of first-in-chain node: the first-in-chain node was determined based on the residual energy of nodes and the distance from node to base station. Herein, the multi-route decay information channel model was employed. The energy consumed for the transmission of data of K bit over a distance of d can be obtained by: $E (k, d) = {\begin{matrix} {kE}_{e} + k ɛ_{fs} d^{2}, & d < d_{0} \\ {kE}_{e} + k ɛ_{amp} d^{4}, & d \geq d_{0} \end{matrix}$ (1) where E_e refers to the energy consumed by sending/acceptance of 1 bit data, ɛ_fs refers to the free space energy model coefficient, ɛ_mp refers to the multi-route decay space energy coefficient, d₀ refers to the maximum transmission distance of the node, namely the critical distance between the sending circuit and the acceptance circuit: $d_{0} = \frac{4 π \sqrt{L} h_{r} h_{t}}{λ}$ (2) where L refers to the transmission loss, h_r refers to the height of the acceptance node, h_t refers to the height of the sending node, λ refers to the wavelength.

According to the model in Equation (1), define Q of a node as: $Q_{i} = w_{i} E_{i} + \frac{w_{2}}{d_{BS} (i)}$ (3)

The node with maximum Q value was selected as the first-in-chain node.

According to the energy model in Equation (1), the energy consumed is related to the square/fourth power of the transmission distance. In Equation (3), w₁ and w₂ were weighed values and w₁ + w₂ = 1; either w₁ or w₂ can be selected and w₁ > w₂. E_i refers to residual energy of the node and d_BS (i) refers to the distance from Node I to base station.

At the data transmission stage, the transmission power of each node was adjusted so that only the closest node receives the signal sent by this node. Owing to the small size of Token, energy consumption in the data transmission process was low. Hence, the Token mechanism was employed at the data transmission stage and the procedures are summarized in Fig. 1.

Fig. 1

Data transmission process.

The first-in-chain node (N₆) generates a Token and sends it to the tip node N₁, which transmit data to Node N₂ along the data chain. Then, the data collected by Node N₂ and sent by Node N₁ was fused and sent to tip node N₃, which sends the Token to Node N₅. Likewise, the data collected by Node N₃ was fused with data sent by Node N₄ and Node N₅ and sent to Node N₆. Finally, the data collected by Node N₆ was fused with data sent by previous nodes and sent to base station. Until then, one data transmission round was completed.

In the presence of a network model with coverage = k, if nodes are homogeneously distributed with in the sensing area density =λ, the node quantity (X) probability follows Poisson distribution [1].

The probability density function is: $P {X = k} = \frac{(λ S)^{k}}{k!} e^{- λ S}$ (4)

The feature function is: $Φ (t) = exp (λ (e^{it} - 1))$ (5)

Set S = 1: $\frac{P {X = k}}{P {X = k - 1}} = \frac{\frac{(λ S)^{k}}{k!} e^{- λ S}}{\frac{(λ S)^{k - 1}}{(k - 1)!} e^{- λ S}} = \frac{λ S}{k} = \frac{λ}{k}$ (6)

If nodes follow Poisson distribution, it is maximized at k = |λ|. The node quantity in an area of S at coverage of f_a is defined N(S). As the node quantity is a random variable that follows Poisson distribution withλ as the parameter, then: $P {N (S) = K} = \frac{e^{- λ S_{s}} (λ S_{s})^{k}}{k!}$ (7)

Define the sensing radius as r, the probability of a random point (W) in the sensing area (S) not being covered can be calculated by: $P = \sum_{k = 0}^{+ \infty} P {N (S) = K} = e^{- λ π r^{2}}$ (8)

Therefore, the coverage in S is can be calculated by: $f_{a} = 1 - P = 1 - e^{- λ π r^{2}}$ (9)

3 Routing algorithm

The collisions, repeated transmissions, and data loss in wireless information channels lead to increased broadband loss. To enhance the network throughput, prescribed transmission attempt rates were employed at the data transmission stage. However, prescribed transmission attempt rates may not be applicable to all WSN and over-high transmission attempt rates result in undesired collision rates [18 –20]. To enhance the routing performances of WSN, dynamic transmission attempt rates were employed: each node in the chain sends slot applications to the node first-in-chain according to its specific conditions, the node first-in-chain releases decision and adjust the time frame length, and the optimal transmission back-off time of undetermined frames according to the quantity of active nodes.

Assume that i refers to the node quantity, M refers to the quantity of active nodes, K = 1 is a constant, $\bar{b}$ refers to the back-off time, P_t refers to the information channel access probability in t. At $P_{t} = \frac{1}{\bar{b} + 1}$ , P-persistent model is approximately an IEEE802.11 with average back-off time of $\bar{b}$ [1]. The initial and real time size of the contention window were defined as CW_min and E_(cw) = 2/p_t - 1, respectively, and E_(CW) < CW_min2^KlogM. The maximum size of the contention window (CW_max) was 1024. Assume that M is sufficient and (1 - x) ^y ≈ e^-xy until the next transmission cycle can be approximated as an exponentially distributed random variable. The probability of successful transmission frame is P_s = M * P_t (1 - P_t) ^M-1 and the probability of idle slots is P_i = (1 - P_t) ^M The probability of nodecollision is:

$P_{c} = \frac{1 - (1 - P)^{M} - M * P_{t} (1 - P_{t})^{M - 1}}{1 - (1 - P_{t})^{M}}$ (10)

Define the current back-off value of Node i as B_i (t), the transmission attempt rate (λ) can be calculated by: $λ (t) = \sum_{i = 1}^{M} \frac{1}{B_{i} (t)}$ (11)

With the average collisions between two consecutive successful transmissions being denoted by a random variable (N_c), the average back-off time $\bar{b} = E [B_{i} (t)]$ can be calculated by: $N_{C} (z) = \sum_{n = 0}^{\infty} P [N_{C} = n] z^{n} = \frac{λ e^{- λ}}{1 - e^{- λ} - (1 - e^{- λ} - λ e^{- λ}) z}$ (12)

According to Equation (12), the average collisions $\bar{n}$ between two consecutive successful transmissions can be calculated by: $\bar{n} = N_{c}^{(1)} (1) = \frac{1 - e^{- λ} - λ e^{- λ}}{λ e^{- λ}}$ (13)

$\bar{cw}$ refers to average quantity of available slots before collisions or successful transmissions and it can be calculated by: $\bar{CW} = \frac{1 - (λ {CW}_{max} + 1) e^{- λ} {CW}_{max}}{λ (1 - e^{- λ} {CW}_{max})}$ (14)

At the chaining stage, the node density was taken into consideration and a threshold distance was designed to control the addition of nodes. Define the chain node quantity as n, then the distance from the first-in-chain node to the nth node is d_n, the overall quantity of nodes in this area is N_node, the length of this area is d: $d i s_{a v e r a g e} = \sum_{n = 1}^{i = 1} d_{n} / (i - 1), n = 1, 2, \dots, i - 1$ (15) $ρ_{node} = \frac{N_{node}}{d}$ (16) $d_{thres} = ρ_{node} \times {dis}_{average} \times α$ (17) where dis_average refers to the average distance between nodes, ρ _node refers to the node density in this area. The threshold distance (α) was set as 1.5.

The procedures of the proposed adaptive back-off adjusted medium access control based chain routing algorithm of wireless sensor are as follows:

Step 1. Parameters are initialized: the node that is farthest to the base station is selected as the tip node of the chain. According to Equation (16), nodes with distances below the threshold distance (d_thres) are added into the chain.

Step 2. The first-in-chain node is selected: According to Equation (3), the node with maximum Q values was selected as the first-in-chain node;

Step 3. The first-in-chain node progresses forwards until access to tip nodes and all nodes involved are labeled as main chain nodes;

Step 4. Nodes in the chain send applications to the first-in-chain node and the first-in-chain node adjust the information received:

Estimate M and calculate the average back-off time $\bar{b}$ according to $λ (t) = \sum_{i = 1}^{M} \frac{1}{B_{i} (t)}$ ;

Calculate the information channel access probability in t (p_t) and size of contention window (E_(CW));

Set the minimum size of contention window as $\frac{E_{(CW)}}{2 {log}^{M}}$ ;

Determine the data frames that have been successfully transmitted based on CW_min and CW_max.

Step 5. The collected data is fused with intrinsic data by the first-in-chain node and sent to base station to finish one data transmission cycle, otherwise go back to Step 1. Repeat Step 1–5 until all data transmission cycles are completed;

Step 6. End.

4 Simulations

Simulations of the proposed algorithm and conventional algorithms were executed and compared with each other. The typical energy model mentioned in Section 2 was employed for simulations. 100∼300 nodes are randomly distributed in an area of 100 m×100 m. Assume M = 110, initial energy of all nodes is 1 J, α= 1.5, the data distribution follows Poisson distribution, the document size is 1000 Byte, the data transmission rate is 1 Mb/s, and the communication rate of information channel is 1 Mb/s. Ranging from 100 s to 3000 s, the file request time is homogeneously distributed and was repeated for three times. Each slot is 2.5 Byte and the overall simulation time was 1 h.

As mentioned in Section 2, chaining in conventional chain routing algorithms is achieved by the greedy method and the chain length is reduced by secondary local

optimization. However, node distribution in WSN is random and communications between one specific node and multiple nodes may be observed if the distances between nodes is the only criterion. As a result, energy consumptions of precursor nodes are accelerated and unexpected failures of precursor nodes may be observed, resulting in increased node energy consumption. The proposed algorithm solved the issue of data concentration by combining average distance between nodes and node density in the area.

Figure 2 shows chaining of the proposed algorithm and conventional chain routing algorithms. As shown in Fig. 2(a), Node 1, 2, 6, 8, 9, and 2 were added into the chain consecutively. According to conventional chain routing algorithms, Node 4 is the node closest to Node 2. The distances from Node 4 to nodes in the chain were calculated consecutively and Node 9, which is closest to Node 4, was selected as the precursor node. Similarly, Node 9 was selected as the precursor node of Node 10. This chaining mechanism can guarantee shorted routes for all nodes in the chain. Nevertheless, Node 9 needs to process data from Nodes 2, 4, and 10 and it may lead to over-concentration of data at Node 9 and unexpected failure of Node 9. As a result of unexpected failure of Node 9, a new precursor node needs to be determined for Nodes 2, 4, and 10, resulting in topological reconstruction of chain leads and increased node energy consumption. As shown in Fig. 2(b), the proposed algorithm achieves network energy consumption reduction and extension of node life cycles.

Fig. 2

Chaining of (a) conventional chain routing algorithm and (b) the proposed algorithm.

Figure 3 shows life cycles of WSN under different threshold distances. At low node densities, the node density has negligible effect on the optimization effectiveness; at high node densities, the threshold distance designed without node density taken into consideration may not lead to appropriate chain structures, resulting in data transmissions between multiple nodes and one specific node and increased frequency of node relocation. As a result, the communication energy consumptions are increased. The threshold distance for long chains is determined based on average distance and node density to minimize data concentration and ratio of long chains.

Fig. 3

Life cycles of WSN under different threshold distances.

Figure 4 summarizes life cycles of WSN in cases of different node distributions created by different algorithms. As observed, the number of transmission cycles in the proposed algorithm before the presence of the first dead node is significantly larger than that in conventional chain routing algorithms and asymptotically optimal back-off algorithm. As the node number increases, average life cycle of WSN in the proposed algorithm was 10% larger than that in conventional chain routing algorithms, indicating that the chaining mechanism of the proposed algorithm reduces probability of long chains and balances size of data processed by each node, thus balancing residual energy of each node. Therefore, it can be concluded that the proposed algorithm can extend life cycle of WSN.

Fig. 4

Life cycles of different algorithms.

Figure 5 shows the effects of the quantity of active nodes on the collision probability. As observed, the collision probabilities in all three algorithms increased with the quantity of active nodes. At quantity of active nodes below 15, the of conventional chain routing algorithm exhibits minimum collision probability; At quantity of active nodes above 23, the proposed algorithm exhibits minimum collision probability and the collision probability in the proposed algorithm increased at a negligible rate as the quantity of active nodes increased, while the collision probabilities of the other two algorithms increased drastically. This indicated that the proposed algorithm can effectively reduce the collision probability.

Fig. 5

Effects of quantity of active nodes on collision probability.

Figure 6 shows the effects of the quantity of active nodes on the access delay. As observed, the increasing rate of access delay in conventional chain routing algorithm was higher than those of asymptotically optimal back-off algorithm and the proposed algorithm. The access delay of the proposed algorithm increased at a relatively low rate as the size of back-off window can be dynamically adjusted in the proposed algorithm, thus reducing network slots.

Fig. 6

Effects of quantity of active nodes on access delay.

5 Conclusions

A novel chain routing algorithm of wireless sensor based on adaptive back-off adjusted medium access control is proposed to improve routing performances of WSN. Herein, dynamic transmission attempt rates were employed: each node in the chain sends slot applications to the node first-in-chain according to its specific conditions, the node first-in-chain releases decision and adjust the time frame length, and the optimal transmission back-off time of undetermined frames according to the quantity of active nodes. In this algorithm, WSN performance indices were proposed by combining area coverage, transmission distance, and residual energy, quantity of collision events and transmission attempt rates were calculated using the adaptive back-off adjusted medium access control, and a chain routing algorithm was established. Additionally, key factors affecting the proposed algorithm were investigated using experimental tests and numerical simulations. The results indicated significant advantages of the proposed algorithm in chaining efficiency, life cycle of nodes, and delay.

Footnotes

Acknowledgments

This work is supported by Special Funds of Applied Science & Technology Research and Development of Guangdong Province, China (Grant:2015B010128015), and Natural Science Foundation of Guangdong Province, China(Grant:2017A030307027).

References

Dan-yang ,

Shuang ,

Song-xiang et al., Research on trust sensing based secure routing mechanism for wireless sensor network, Journal on Communications38(10) (2017), 60–70.

Quan and

Hong , Dynamic switching based real-time routing in low-duty-cycle wireless sensor networks, Journal on Communications36(10) (2015), 224–234.

Cordasco and

Wetzel , Cryptographic versus trust-based methods for MANET routing security, Electronic Notes in Theoretical Computer Science197(2) (2008), 131–140.

Marchangl and

Datta , Light-weight trust-based routing protocol for mobile ad hoc networks, IET Information Security6(2) (2012), 77–83.

Qin ,

Wei-dong ,

Lan-xin et al., Rotation-based WSN chain routing protocol, Journal of University of Electronic Science and Technology of China2(44) (2015), 195–200.

Xihuang and

Cuifang , Improved density-based routing algorithm for wireless sensor networks, Computer Applications10(27) (2007), 2549–2551.

Liangrui ,

Yuanyuan and

Sen , A chain routing algorithm based on evidence theory in wireless sensor networks, Journal of computer research and development50(7) (2013), 1362–1369.

Peng-fei ,

Ming ,

Yun-zhuo et al., The dynamic wireless sensor network routing protocol based on prime-numbered addresses, Journal of University of Electronic Science and Technology of China5(44) (2015), 757–763.

Jianling ,

Yongchao and

Zhi , Multi-round cluster based multi-hop clusting routing protocol for wireless sensor networks, Computer Science7(40) (2013), 67–97.

10.

Yingchi ,

Jiulong ,

Kang et al., Hierarchical routing protocol based on link quality in wireless sensor network, Computer Science3(42) (2015), 74–80.

11.

Mengying ,

Xin and

Hua , Cluster-chain based low-energy consumption hierarchical routing protocol, Computer Science11(42) (2015), 144–148.

12.

Tao ,

Hui and

Jun-yan , A wireless sensor network routing algorithm based on 3D cell space, Journal of Electronics & Information Technology6(35) (2013), 1298–1304.

13.

Xiaojun and

Pengfei , Routing and clustering algorithm heterogeneous wireless sensor networks based on gravitational search algorithm, Control and Decision3(32) (2017), 564–569.

14.

Qiang ,

Wei-Hua and

Jin-Feng , New RSSI based routing protocol in wireless sensor networks, Journal of Chinese computer Systems9(32) (2011), 1832–1836.

15.

Xiang and

Huazhi , Algorithm of wireless sensor network routing based on energy aware, Computer Science43(6A) (2016), 290–294.

16.

Hongwei ,

Ming and

Caixia , THO-MAC: A low-latency and energy-efficient MAC protocol with two-hop optimization in WSNs, Journal of National University of Defense Technology36(1) (2014), 161–166.

17.

Chun-sheng ,

Qi-zhi ,

Ru-po et al., Simulation of real-time wireless LAN MAC protocol, Journal of System Simulation17(3) (2005), 718–721.

18.

Biao ,

Chen ,

Jian et al., Multi-hop routing algorithm for wireless sensor networks based on uneven clustering, Computer Science44(2) (2017), 157–162.

19.

Zhouzhou and

Yang , Clustering routing algorithm for wireless sensor networks based on S-PSO, Journal of Chinese Computer Systems38(10) (2017), 2207–2210.

20.

Lei ,

Haixia and

Jiangbo , Wireless sensor routing algorithm based on optimal distance and cell clustering, Computer Engineering and Design38(4) (2017), 888–892.