TMCnet News
Energy-Efficient Routing over Lossy Links in Wireless Sensor Networks [Sensors & Transducers (Canada)](Sensors & Transducers (Canada) Via Acquire Media NewsEdge) Abstract: In many applications of wireless sensor networks, sensor nodes are randomly scattered in some regions. Different pairs of nodes consume different energy for communication in term of different distance and environments. In this paper, we propose using bit errors to choose appropriate power level. Compared to other estimators, bit errors can directly reflect the wireless channel state and can be used in more complex regions. In order to search an energy efficient path, we translate power levels to PL_Dis (power level distance) and use PL_Dis between sensor nodes to set up a PL_Dis graph. We also propose local shortest path algorithm (LSPA) in PL_Dis graph, which is a distributed routing protocol algorithm, to choose a short PL_Dis path for very sensor node to the base station. Simulation shows that compared to different routing protocol schemes, our scheme can choose efficient paths to the base station and our scheme can greatly reduce transmission energy and prolong WSNs lifetime. Copyright © 2014 IFSA Publishing, S. L. Keywords: Wireless sensor networks, Power level control, Routing protocol, Data transfer, Lossy links. (ProQuest: ... denotes formulae omitted.) 1. Introduction The availability of micro-electro-mechanical devices and wireless interconnected devices has fostered the development of Wireless Sensor Networks (WSNs). Sensor nodes in many WSNs applications are randomly scattered in various regions, such as forest, valley, farmland, and so on, to measure physical parameters and to transmit the collected data to a base station. Data transmission for wireless sensor networks differs substantially from that of wire networks because of instability of wireless channel and severe energy constraints of battery-powered sensor nodes. The quality of wireless communication depends on the environment, such as the frequency spectrum, noises, and so on. Since sensor nodes in many applications are randomly scattered in various regions and their communication distance and peripheral environment are different, different pairs of sensor nodes have different link quality. In this paper, we explore inspection methods for evaluating link quality and routing protocol for transmission data in lossy wireless channel. The rest of this paper is organized as follows: we review previous related works of routing protocol in wireless sensor networks in Section 2; we propose a routing protocol scheme EERP (Energy Efficient Routing Protocol) in Section 3; then we evaluate EERP scheme by simulation in Section 4; in Section 5, we conclude the paper. 2. Related Work Many routing protocol have been designed for WSNs. The routing protocol algorithms may be classified as centralized and distributed. In the centralized algorithms, a particular sensor node is responsible for optimizing routing protocol, such as LEACH [1] and CODA [2], The centralized algorithms may have better performance in term of saving energy and prolonging the network lifetime. However, since the centralized algorithms rely on global information of WSNs and require high processing power and storage, they are hard to implement in a large-scale sensor network. Distributed routing protocol algorithms rely only on local parameters and are executed on each sensor node to achieve an ideal routing protocol. The main component of most distributed routing protocols is a greedy forwarding mechanism by using the local parameters of sensor nodes to move the packet closer to the base station at each hop. The most popular parameters are sensor node's location [3-4], signal strength [5-7], and distance to neighbors [8], etc. However, Most of routing protocols now are based on a simplifying idealized assumption that there are perfect links between pairs of sensor nodes within a given communication range, but beyond which there is no link. If sensor nodes are randomly scattered in various regions and their communication distance and peripheral environment, different pairs of sensor nodes have different link quality. Several researchers [9-10] also pointed out that the use of simple radio models may lead to wrong simulation results. As an electromagnetic signal may be reflected, diffracted, and scattered in the process of propagation, the signal strength decays with respect to distance. Experimental studies [10-12] identify the existence of three distinct reception regions in the wireless link: connected, transitional and disconnected. Disconnected region is the region in which the sensor nodes have low packet reception ratio (PER). However, the sensor nodes in connected region have high packet reception ratio. The transitional region resides between the connected and disconnected regions, where the variance of the PER is high. Since sensor nodes in WSNs are usually battery equipped and they have a limited amount of energy, they should choose energy efficiency method to transfer data. Signal strength may be attenuated and interfered in the process of transmission. When the signal strength is attenuated to some level, it easily cause bit errors. The more signal strength lost, the more bit errors will occur. There are three basic methods to resolve the problems: Automatic Repeat Request (ARQ), Forward Error Control (FEC) and enhance emission power. ARQ supposes a receiver will acknowledge a data from a sender and the sender will retransmit the data if it is not acknowledged within a period time. FEC uses redundant information along with the data to recover the damaged packets. Enhancing emission power will increase the receiver's signal strength and improve transmission quality. As different pairs of sensor nodes may have different transmission environments, in this paper, we use choosing power level according the channel state to transmission data in lossy links. We will study how to build routing protocol based on various links quality to improve transmission performance 3. Energy-Efficient Routing Protocol In order to choose an efficient routing to the base station, the sensor nodes of WSNs first need estimate the link quality with their neighbors. Some research uses received signal strength as an indication of link quality. However, paper [9] suggests that signal strength can be a poor indicator in link quality. Lognormal shadowing path loss model [13] provides the relations between distance and received signal strength. Some research based on the model uses position or distance to estimate link quality. However, as sensor nodes in WSNs may be randomly scattered in different peripheral environments, interference signal factors, such as reflecting, diffracting, scattering and so on, may be significantly different. The empirical observation in [14] also pointed out that the path-loss exponent and shadowing variance of log-normal shadowing path loss model change drastically in different location. It is hard to use a simple model to estimate link quality for all pairs of sensor nodes. As bit errors can directly obtain wireless channel state, in this paper, we use bit errors to inspect link quality. Now most the radio power of sensor nodes can be controlled. For instance, Berkeley Motes [15] have in total 100 power levels. In order to save energy and prolong lifetime of WSNs, we adopt adjusting the radio power for a pair of sensor nodes according their wireless channel state by measuring bit errors. 3.1. Choosing Power Level in Single-Hop A pair of sensor nodes should choose an appropriate power level in the process of transmission. If the power level selected is too high it will causes much power waste. On the other hand, when the power level is too low it will cause much packets lost, because the power is not strong enough to transmit packets. In this paper, we use statistic bit errors of a number of packets to choose power level. Suppose we use a correction code BCH (n, k, t) to detect errors and correct errors in the process transmission. The three fields in the parenthesis indicate the number of block bits, data bits, and the maximum number of corrupted bits to be recovered, to detect errors and correct errors in the process transmission. If bit errors in a packet are less than t, we consider it as a valid packet. Suppose T is the threshold of choosing power level. We count the number of valid packets after receiving a group of packets to choose power level, as shown in Algorithm 1. Algorithm 1: Choosing Power Level Input: the number of statistical packets N; maximum number of corrupted bits t; choosing threshold T Output: power level 1: pass=0 2: level=l 3: While pass=0 do 4: the sender send N packets to the receiver, the receiver count the number of valid packets n; 5: if n<T then 6: level++; 7: else 8: pass=l; 9: end if 10: end while As in the process of transmission data may have Gaussian random noise and produce more bit errors, T usually choose a high value to eliminate the influence of random noise. 3.2. Level Distance Link Graph Building and Paths Selection As in the process of transmission data may have Gaussian random noise and produce more bit errors, T usually choose a high value to eliminate the influence of random noise. In WSNs, routing protocol should be energy efficient to prolong the sensor network lifetime. EERP uses PL_Dis (power level distance) which is translated from power level as the primarily parameter for next hop selection. Different power level will consume different mount of energy transmission data and provide different transmission quality. If a pair of sensor nodes choose level L as transmit power, the PL_Dis of the pair sensor nodes is the energy cost per bit transmitted. If PL_Dis of a pair of sensor nodes is high, they consume more energy for transmission data. EERP uses PL_Dis as weight to build link graph. Very sensor node shares PL_Dis with its neighbors, then WSNs sets up a PL_ Dis graph. If a sensor node chooses a short path to the base station in PL_Dis graph, it can consume less transmission energy and prolong network time. Dijkstra algorithm [16] is probably the best-known shortest path algorithm. However, a path algorithm in WSNs should be of relatively low complexity, since a typical wireless sensor node currently has low processing power and a small memory. As Dijkstra algorithm requires global information and high processing power and storage, it is hard to implement in WSNs. EERP uses LSPA (local shortest path algorithm), which is a distributed routing protocol algorithm, to choose a short PL Dis path to the base station. Layer information is used to implement LSPA. At the beginning of LSPA, the base station broadcasts the Layer_MSG (0) within radio range to its all neighbors. After received the message, every neighbor of the base station broadcasts the Layer MSG (1) to all its neighbors, and so on. When a sensor node receives more than one Layer_MSG messages from its neighbors, it selects the minimal one and adds one to the Layer_MSG as its Layer MSG, then broadcasts its Layer MSG to all its neighbors. LSPA uses parameter NTBE_Dis, which indicates the total PLDis consumption for transmission data to the base station, to choose next hop. At beginning, very sensor node initializes the parameter NTBE_D is to co and the base station set the parameter to 0. When a sensor node computes it's NTBE_Dis and to choose next hop, it needs at least one sensor nodes in its local PL_ Dis graph and those sensor nodes have calculated their NTBE_Dis. In EERP scheme, those sensor nodes, whose Layer_MSG is 1, first calculate their NTBE_Dis and choose the next hop, then the sensor nodes has Layer_MSG 2 do so, and so on. A sensor node u uses the following algorithm to calculate its NTBE_Dis and to choose the next hop. Algorithm 2: LSPA algorithm 1: for each sensor node v in the local PL_ Dis graph of u, u using Dijkstra algorithm to search the shortest PL_ Dis distance NTNE (u, v) to v and calculates: NNBE (u, v)=NTNE (u, v)+NTBE_Dis_v 2: u selects the minimal NNBE (u, v) as its NTBE_Dis and chooses v as the next hop to the base station. The size of local PL_ Dis graph is important to routing protocol. If the size is too big, it is hard for EERP to implement LSPA in WSNs, because sensor nodes in WSNs only have low processing power and a small memory. On the other hand, when the size is too small EERP possibly cannot search an efficient path. In LSPA, the local PL_Dis graph of u is a subgraph of the global PL_ Dis graph. The sensor nodes in local PL_ Dis graph are closer to u and their Layer_MSG distance between the Layer_MSG of u is less than or equal to a parameter S_r. If WSNs implements Level 1, Level 2, Level n as transmission energy, S_r is given by: ... (1) where the floor( ) function returns the largest integer that is less than or equal to the input number. 4. Simulations In this section, we perform simulation to measure the performance of our proposed scheme. We use the log-normal shadowing model [13], the noise floor [13] and the probability of bit errors for non-coherent FSK [17] to simulate experiment environment, and then we validate our routing protocol. 4.1. Wireless Channel Error Model When an electromagnetic signal propagates, the signal strength decays exponentially with respect to distance. At the same time, for a given distance d, the signal strength is random and log-normally distributed about the mean distance-dependent value. The log-normal shadowing path loss model is one of the most common radio propagation models. The model is given by: ... (2) where d is the receiver distance, n is the path loss exponent, Xa is the zero-mean Gaussian random variable (in dB) with standard deviation g (multipath effects), d_0 is the reference distance and PL(d_0) the power decay for the d_0 distance. Given a transmitting power P_t, the received signal strength for the distance d is (all powers in dB): ... (3) where P_n is the noise floor. As the signal strength may be attenuated and interfered by noise when it propagates, the wireless link is error prone. In the presence of additive white Gaussian noise the probability of bit errors for noncoherent FSK is given by: ... (4) where R is the data rate in bits, and B_N is the noise bandwidth. 4.2. Simulation Parameters In the simulation, 300, 400, 500, 600 and 700 sensor nodes are randomly distributed in a 1000 m x 1000 m region and we randomly choose a sensor node as the base station (sink). The maximal transmission range is 100 m for all sensor nodes. We choose 5 power levels, which is based on mica2 platform to transmit data. Different power levels consume different energy for transmission a bit data. The energy cost per bit transmitted is given by [18]: ... (5) The 5 power levels and the consumption energy are shown in Table 2. The parameters S_r of the loca PL_Dis graph is 3 according to Formula (1). 4.3. Simulation Results At beginning, every sensor nodes initialize power level with its all neighbor. Every sensor node sends 100 (N) same packets, 31 zeros, to its entire neighbor. The bit error rate of a packet is according to Formula (4). Then very neighbor calculates bit errors of every packet and choose a power level according to Algorithm 1. The simulation chooses the correction code choose BCH (31, 26, 1) and the T is set 70. Then we get PL_Dis graph. To evaluate the performance of our proposed routing protocol, we compare EERP scheme with layer routing scheme and geographical routing scheme. Layer routing scheme uses static power level. In order to implement transmission task, layer routing scheme choose power level 5. The transmission path of layer routing scheme is that very sensor node only sends data to a neighbor whose Layer_MSG is smaller than the sender. Geographical routing scheme also uses static power level (power level 5) and uses the shortest path algorithm to select path in a geographical graph. In the simulation, very sensor node transmits a packet data to the base station along paths selected by different schemes and calculates transmission packets. The total energy consumed is shown in Fig. 1. Layer routing scheme can easily get layer path by broadcasting Layer_MSG and may transmit data to the base station along the layer path. However, layer routing scheme does not choose path according to wireless channel state, as shows in Fig. 1, energy consumption of layer routing scheme is about 58 % more than that of EERP scheme in 300 sensor nodes and about 51 % more than that of EERP scheme in 700 sensor nodes. Geographical routing scheme also consumes more energy, and energy consumption of geographical routing scheme is about 0.63 times more than that of EERP scheme in 300 sensor nodes and 0.73 times more than that of EERP scheme. Compared to layer routing scheme and geographical routing scheme, EERP scheme saves much energy. EERP, as a distributed routing protocol, also can be easily implemented in WSNs. 5. Conclusions In this paper, we present EERP, a novel energy efficient routing protocol scheme. Different wireless channel states should use various power levels to transmission data. In our scheme, we use bit errors of packets to choose power level according to wireless channel state. Compared to other estimators, bit errors can directly reflect the wireless channel state and can be used in complex regions. In this paper, we use parameter energy consumption (PL_Dis) to set up a PL_Dis graph. We also propose LSPA in E_Dis graph to find an efficient way to the base station. As LSPA is a distributed algorithm, it can be easily implemented in WSNs. Simulation shows that compared to different routing protocol scheme, EERP scheme can saves much energy and provides well transmission performance. Acknowledgment This work is supported by the project of national sparking plan project (Project Name: Using Wireless Image Sensor Networks to Monitor Fruit and Vegetable Pests, Contact Number: 2011BAD21B01). References [1]. W. R. Heinzelman, A. Chandrakasan, H. Balakrishnan, Energy-efficient communication protocol for wireless microsensor networks, in Proceedings of the Hawaii International Conference on System Sciences, 2000, pp. 3005-3014. [2] . S. Lee, J. Yoo, T. Chung, Distance-based energy efficient clustering for wireless sensor networks, in Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04), 2004, pp. 567-568. [3] . B. Karp, H. T. Kung, Gpsr: Greedy perimeter stateless routing for wireless networks, in Proceedings of Sixth Annual International Conference on Mobile Computing and Networking, 2000, pp. 243-254. [4] . Y. Xu, J. Heidemann, D. Estrin, Geography-informed energy conservation for ad-hoc routing, in Proceedings of the Seventh Annual ACM/IEEE International Conference on Mobile Computing and Networking, 2001, pp. 70-84. [5] . C.-W. Chen, C.-C. Weng, Y.-C. Kuo, Signal strength based routing for power saving in mobile ad hoc networks, Journal of Systems and Software, Vol. 83, No. 8, 2010, pp. 1373-1386. [6] . L. Vespa, K. Mei, R. Maitree, N. Weng, Signal strength analysis for optimal routing in wireless sensor networks, in Proceedings of IEEE Region 5 Conference, 2008, pp. 17-20. [7] . M. Liu, J. Cao, G. Chen, X. Wang, An energy-aware routing protocol in wireless sensor networks, Sensors, Vol. 9, Issue 1,2009, pp. 445-462. [8] . S. Capkun, M. Hamdi, J. Hubau, Gps-free positioning in mobile ad-hoc networks, in Proceedings of the 34th Annual Hawaii International Conference on System Sciences, 2001, pp. 3481-3490. [9] . D. S. J. D. Couto, D. Aguayo, B. A. Chambers, R. Morris, Performance of multihop wireless networks: shortest path is not enough, Computer Communication Review, ACM, Vol. 33, Issue 1, 2003, pp. 83-88. [10] . D. Ganesan, B. Krishnamachari, A. Woo, D. Culler, D. Estrin, S. Wicker, Complex behavior at scale: An experimental study of low-power wireless sensor networks, UCLA CS Technical Report UCLAJCSDTR 02-0013, 2002. [11] . J. Zhao, R. Govindan, Understanding packet delivery performance in dense wireless sensor networks, in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, 2003, pp. 1-13. [12] . A. Woo, T. Tong, D. Culler, Taming the underlying issues for reliable multihop routing in sensor networks, in Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, 2003, pp. 14-27. [13] . T. S. Rappaport, Wireless Communications: Principles and Practice, Prentic Hall, New Jersey, 1996. [14] . K. Sohrabi, B. Manriquez, G. Pottie, Near ground wideband channel measurement in 800-1000 mhz, in Proceedings of IEEE Transactions on Vehicular Technology, 1999, pp. 571-574. [15] . H. Jason , S. Robert ,W. Alec, H. Seth, C. David, P. Kristofer, System architecture directions for networked sensors, ACM SIGPLANNotices, Vol. 35, No. 11,2000, pp. 93-104. [16] . E. W. Dijkstra, A note on two problems in connexion with graphs, Numerische Math, 1, 1959, pp. 269-271. [17] . P. Z. Peebles, Digital Communication Systems, Prentic Hall, 1987. [18] . M. G. C. Torres, Energy consumption in wireless sensor networks using GSP, Tech. Rep., Universidad Pontificia Bolivariana, 2006. 1 Liankuan ZHANG,2 Jiuhao LI 1 Department of Mathematics, South China Agricultural University, Guangzhou, 510642, China 2 Department of Water Conservancy and Civil Engineering, South China Agricultural University, Guangzhou, 510642, China 1 Tel.: 020-85280319, fax: 020-85280319 1 E-mail: [email protected] Received: 21 June 2014 /Accepted: 29 August 2014 /Published: 30 September 2014 (c) 2014 IFSA Publishing, S.L. |