A Passive Maintenance Routing Protocol for Wireless Sensor Networks

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 C_i be the number of packet retransmissions in the ith time window. H_i is a value between C_i and history retransmissions, H_i can be expressed as:

(1)

(2)

where, 0 <a <1 and 0 <b <1 both are tuning parameters, T_i is a threshold. In the time window t, if H_i is greater than T_i-1, the route maintenance is triggered and H_i will be reset to 0 in next round estimation. To understand Eq. 1 and 2, for example, let C_i 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 T_i-1 = 0, C_i 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