Abstract: Most data collection routing protocols in wireless sensor networks adopt periodic routing maintenance mechanism. The mechanism is not energy efficient for environment monitoring deployments. Sometimes, the energy dissipation for routing maintenance is more than the sensing data transmission. This study proposes a passive maintenance routing protocol for wireless sensor networks. The protocol estimates the communication link quality by monitoring the retransmission of collection data packets and its routing maintenance is triggered when the poor link quality is detected. The routing protocol is implemented in TinyOS system and evaluated through simulations.
INTRODUCTION
Deployments of wireless sensor networks (Singhal et al., 2012) in recent years have grown steadily in their functionality and scale but they still operate under extreme energy constraints. One of mainly energy consumption processing is the control message exchange, which is used for construction and maintenance of network’s routing, synchronization, scheduling, etc. Hence, the ability to efficiently decrease control message communication while still insure the service quality within the sensor network remains paramount.
The routing protocol in wireless sensor networks (Singh et al., 2010; Saleem et al., 2011; Karp and Kung, 2000) can divide into two categories according to the style of routing maintenance: the active way and passive way. For the active maintenance, after finish construction of whole routing topology, each node needs to send beacon message period to maintenance the routing. While for the passive routing maintenance schema, routing is not actively updated after the process of routing construction; only when the route is invalid or the link quality is decreased observably, the routing protocol starts routing repair process to get a better path. Now available data collection routing protocols almost are active maintenance routing protocols, such as MintRoute (Woo and Culler, 2003), CTP (Gnawali et al., 2009), etc.
Deployment wireless sensor network for environmental monitoring applications, such as supervision of building (Torfs et al., 2013) and city climate monitoring (Hu et al., 2011), the communication link is usually stable and the sample period is relatively long interval, usually 5-30 min. If the routing update interval set too short, the control packets are exchanged frequently, sometimes the energy consumption of control packets even bigger than sensing data packet transmission. If the routing update interval set too long, the effect of routing maintain will decrease and can’t reflect the link quality change in real time.
This study proposes a Passive Maintenance Routing protocol (PMR, for short) for wireless sensor networks, which updates routing protocol when the link quality decline or the link invalid. PMR is an effective way to reduce control packets energy dissipation and sustain the stability of network connectivity.
PASSIVE MAINTENANCE ROUTING
Route selection: For environmental monitoring applications, user hopes to construct the routing tree over the network quickly after deployment. So in the process of routing construction, should set the frequency of the control message exchange quickly that establish the routing topology as soon as possible. However, after the routing topology becomes stable, need to reduce control packet exchange. This is beneficial to conserve energy consumption to longing network lifetime.
In PMR, beacons are divided into three categories: Request, reply and pull. All of these beacons are transmitted by one hop broadcasting. A request beacon is to advertise that the sender doesn’t have a proper parent and it is searching for a parent. A reply beacon is to indicate that the sender has a route to BS and can be a candidate parent. Finally, a pull beacon indicates that the sender has better or updated route information and notifies its neighbors to maintain their routes.
After sensor deployment, only BS has a parent which is an upper computer connected over UART. Other nodes do not have parents and broadcast requests periodically. When BS receives the requests from the nodes closer to it, it sends reply beacons. After enough exchanges of the beacons, the sensor nodes at the 1st level in the routing tree choose BS as parent and stop sending requests. Similarly the nodes at the 2nd level exchange request and reply beacons with the nodes at the 1st level to determine their parent. The whole routing tree can be constructed after several rounds. When the routing tree is constructed, none of the nodes in the network send request beacons. If the communication links in the network remain good, there will be no beacon exchange at all and the link quality is estimated by transmitted data.
Link estimation: Since PMR uses acknowledge and retransmission schemes for data packets transmission, the decline of link quality increases the number of retransmissions and packet drops. The link quality is estimated by observing the number of packet retransmissions. PMR uses the window mean with EWMA (exponentially weighted moving average) as link quality estimator (Woo et al., 2003) which computes an average retransmission rate over a time period and smoothes the average by EWMA.
Let i be the index of a time window and t be the time window represented in the number of message transmissions and Ci be the number of packet retransmissions in the ith time window. Hi is a value between Ci and history retransmissions, Hi can be expressed as:
| (1) |
| (2) |
where, 0 <a <1 and 0 <b <1 both are tuning parameters, Ti is a threshold. In the time window t, if Hi is greater than Ti-1, the route maintenance is triggered and Hi will be reset to 0 in next round estimation. To understand Eq. 1 and 2, for example, let Ci be a random value between 7 and 10, a = 0.5 and b = 0.1. Table 1 shows the retransmission result of 5 time windows. In the 3rd and 5th windows, the number of retransmissions is greater than the threshold and routing maintenance is triggered.
From Table 1, there has a problem in the link estimator. When Ti-1 = 0, Ci has a useless reference value and the estimator will never be able to detect the decrease of link quality in the current time window.
| Table 1: | Process of link estimation |
To solve the problem, PMR uses two criteria for routing maintenance. One is the estimator mentioned above. The other is data packet drop rate. For example, when the packet drop rate is greater than 10% (according to the reliability level of the user requirement) in a time window, the routing maintenance process will be triggered.
Route maintenance: In PMR, the route maintenance of a node is triggered under the following events:
| • | When a node’s link quality to its parent gets worse or the link has failed |
| • | When a node receives a pull beacon |
After routing maintenance has been triggered, a node sends request beacons periodically to select a proper parent. If it finds a parent and the route cost to BS is significantly decreased (PMR chooses 20% decrease as threshold), the node broadcasts this event using pull beacons because it may provide a better route for nearby nodes. On the other hand, if the new route cost is significantly increased (PMR chooses 20% increase as threshold) or it cannot find a parent, the node also informs the event to its children using pull beacons so that they will adjust the network topology in time.
The scene of route failure is demonstrated in Fig. 1a. The link quality between node D and its parent B is estimated to be worse by transmitted data packets, and routing maintenance is triggered. As shown in Fig. 1b, C is selected as its new parent.
As shown in Fig. 2a, when node C detects that node A is removed or failed, it can’t find an available parent in its communication range. C tells its children E and F that the route is invalid by broadcasting pull beacons. Routing maintenance of E and F is triggered and a new routing tree is reconstructed as shown in Fig. 2b.
When a new node joins network, routing maintenance is triggered. As shown in Fig. 3a, node F is a new node and its parent is BS. F broadcasts pull beacons. D receives the pull beacons and routing maintenance process is triggered. Eventually D chooses F as its new parent, as shown in Fig. 3b. If the change in link cost is significant (20%), D will inform its neighbors the cost change by pull beacons.
| Fig. 1(a-b): | The first case of routing maintenance, (a) Node D disconnect the connection with the node B and (b) Node D changes parent |
| Fig. 2(a-b): | The second case of routing maintenance, (a) Node A is removed and (b) The subtree updates routes |
| Fig. 3(a-b): | The third case of routing maintenance, (a) A new node F joins network and (b) Node D updates route |
RESULTS AND DISCUSSION
In this section, PMR is evaluated in simulations. A prototype was implemented in TinyOS (Levis et al., 2005). PMR is compared to MintRoute routing protocol, in terms of reliability and energy efficiency.
| Fig. 4: | PMR's beaconing rate decreases and stabilizes over time. It is significantly smaller than MintRoute's over the long run |
TOSSIM (Levis et al., 2003) is used in all simulations which is a discrete event-based simulator for TinyOS. TOSSIM requires a user specify the signal attenuation levels for every network link. This work used the Log Distance Path Loss model to calculate these attenuations. One hundred sensor nodes and one BS are deployed in an area of (50, 50 m), the BS placed at (0, 0).
The number of beacons for PMR and MintRoute are shown in Fig. 4. The beaconing rate of PMR is high during network startup because every node is busy with exchanging beacons to discover the routes and construct the network. The beaconing rate decreases after a period of time, because in PMR beacons are only sent when the route needs to be maintained. In MintRoute, beacons are sent at a fixed interval of 1 min. PMR has a much less number of control packet transmissions than MintRoute. The ability of route failure recovery is studied by running PMR and MintRoute for 25 min with a packet transmission interval of 10 sec. After 10 min, five nodes are removed that are forwarding most of the packets in the network. The simulation results are shown in Fig. 5. It shows that PMR has only a small drop in delivery ratio at 12 min. This is because when a node detects a route failure, it transmits beacons periodically with an interval of several hundred milliseconds. Thus the failure route can be repaired quickly. However, the delivery ratio for MintRoute is 55%. This is because MintRoute sends beacons every 1 min. Therefore it needs several minutes to repair the failure.
The energy consumption for PMR and MintRoute is studied by the following simulations. Sensor nodes generate sensing data every 30 sec and MintRoute beaconing interval is 1 min.
| Fig. 5: | PMR has a consistently higher delivery ratio than MintRoute |
| Fig. 6: | PMR’s cost is lower than MintRoute and the portion of that is control is 60% lower |
Figure 6 compares the energy consumption of delivering each data packet from source node to BS for PMR and MintRoute. It shows that control packets for PMR are much less than those for the MintRoute (3 vs. 7.2%). The decrease in the number of control packets is due to the passive maintenance routing protocol, where beacon exchange happens only when a route needs to repair.
CONCLUSION
This study proposed a passive maintenance routing protocol. Instead of using periodic beaconing to estimate link quality and maintain network routing topology, PMR estimates the link quality by monitoring the retransmission of collection data packets and its routing maintenance is triggered when poor link quality is detected. Therefore the energy dissipation due to beacons can be diminished.
ACKNOWLEDGMENTS
The work is supported by the Key Laboratory Promotion Project of Shenzhen (Grant No. CXB201104220033A) and the Technology Research and Development Project of Shenzhen (Grant No. CXZZ20120831173053551).