1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
A hybrid routing protocol for wireless sensor networks with mobile sinks
1Veena Safdar, 1,2Faisal Bashir, 1Zara Hamid, 1Hammad Afzal and 2Jae Young Pyun
1Dept. of Computer Science, National University of Sciences and Technology (NUST), Islamabad, Pakistan
2Dept. of Information & Communication Engineering, Chosun University, South Korea
veenasafdar@gmail.com, faisalbashir@mcs.edu.pk, xarahamid@yahoo.com, hammad.afzal@mcs.nust.edu.pk, jypun@chosun.ac.kr
Abstract— Low power and lossy networks have been an active area of research due to their large number of potential applications in different environments like health, environment monitoring and entertainment domain. Numbers of protocols have been proposed for routing in these networks using metrics like hop count, delay, bandwidth etc. The working group of IETF has done one major contribution in form of a proactive gradient based routing protocol for low power and lossy networks (RPL). However, for a network having few mobile sinks calculating gradients using proactive approach is costly in terms of energy. This paper proposes a hybrid routing protocol for wireless sensor networks with mobile sinks. It proposes a combination of reactive and proactive approach to enhance RPL for efficiently handling movement of multiple sinks.
DAGs are only maintained by nodes close to the sink within a certain zone. While the nodes outside the zone use on demand sink discovery to find the closest possible sink, without maintaining DAG. The frequency of zone creation messages and zone sizes can increase or decrease depending on the speed of sink. This helps to decrease the number of retransmissions resulting in low standing cost for maintain DAGs and enhances the network life time especially under average or high mobility of sink.
Index Terms—Wireless sensor networks, Mobile sinks, RPL Introduction
Sensor networks are the key to gathering the information needed by smart environments, whether in buildings, utilities, industrial, home, automated transportation systems and many more. Recently many practical scenarios require distributed networks of sensors that can be deployed and have self-organizing capabilities.
These networks are generally characterised as Low power and Lossy Networks (LLNs) because the sensor nodes have limited battery power, processing capability and memory.
Moreover, the wireless links between devices are characterized by high loss rates, low data rates and instability.
Network can consist of hundreds of nodes that can act as a source node as well as a relaying node to forward data to sink. As a result of frequent data transmission to a single sink node, the nodes close to sink are repeatedly used for data forwarding to the sink. Hence, energy of theses nodes is quickly depleted, causing holes near the sink [5]. Different techniques have been proposed to solve this problem. One way to solve this problem is to have mobile sink(s). This technique involves controlled movement of sink toward nodes having higher energy for even distribution of energy in the network and to avoid network partitioning. Mobility of
sinks in wireless sensor networks has attracted a lot of attention in recent years and many proposals have been put forward to handle its challenges and use it as a tool to evenly utilize energy [1][2][6][9].
Apart from using sink mobility as tool for avoiding network holes, in many applications, a sink is mounted on some moving device or human beings. For example, in a building security system, sensor nodes detect unwanted activities and intrusions while security officials acting as mobile sinks are required to receive this information. So it is vital for a sensor node to detect an event and report it to the closet sink (security official) for a prompt action.
IETF’s working group for routing on low power and lossy networks has been working on designing a routing protocol for these networks that resulted in a proposed protocol RPL (IPv6 Routing Protocol for Low power and lossy networks) [3, 10]. It is targeted at IPv6-based wireless sensor networks with thousands of sensors and supports a variety of applications including industrial, urban, commercial, home buildings, etc. RPL is generally a proactive routing protocol where a sink broadcasts its presence periodically which is further propagated by the nodes in the network. Nodes use these messages to construct DAG (Directed Acyclic Graph) to the sink. In RPL for supporting sink mobility, a sink needs to advertise frequently which can not only enhance the network traffic but will also increase the energy expenditure.
In this paper, a hybrid (reactive and proactive) routing protocol has been presented that enhances RPL to efficiently support mobile sinks. In this approach, the sink presence messages are only issued for a confined zone consisting of few hops. The frequency of these messages as well as the zone size depends on sink mobility. Nodes within the zone maintain active DAGs up to the root node (closest sink). A node not having an active DAG does not belong to any zone, therefore, it uses on-demand sink discovery where any node having an active DAG can reply. This approach reduces the standing energy cost, since DAG maintenance is only done by zone nodes. In case of high sink mobility paths to the sink will frequently change therefore small zones are created but for low mobility bigger zones can be created for prompt data delivery to sink node.
The rest of paper is organized as follows: Brief discussion on RPL protocol and research work related to mobile sinks and various proposed protocols are discussed in section II; section III describes basic model and assumptions
ISWPC 2012 1569588751
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
of this proposed idea; section IV presents the operation of the proposed hybrid routing protocol; in the last section conclusion and future directions are discussed.
II. RELATED WORK
In this section, various research works with respect to mobile sinks in wireless sensor networks are examined and analysed to show how these approaches deal with sink mobility. Routing protocol for low power and lossy networks RPL is also briefly discussed with its basic mechanism.
IETF ROLL working group is doing efforts and contributing to standardize a routing protocol for low power and lossy networks and one such effort is RPL [12]. RPL is a routing protocol designed for low power and lossy networks with thousands of resource constrained nodes. RPL organizes nodes into a DODAG (Destination Oriented DAGs) rooted towards one DAG root (Sink) identified by a unique identifier DODAGID. The DODAGs are optimized according to an objective function which specifies the constraints and the metrics in use (e.g., hop count, latency, node energy). Each node is assigned a height (rank) which determines its relative position in the DODAG. The rank increases down the DAG and decreases up. RPL constructs and maintains the upward routes of the DODAGs by the transmission of DODAG Information Object (DIO) messages. Destination Advertisement Object (DAO) messages are aimed to maintain downward routes. The transmission of DIO messages by a node is regulated by a trickle timer to suppress redundant control messages.
Sending a packet to the DAG ROOT consists in selecting the preferred parent from the list of parents with lower rank [3, 10]. This effort of IETF ROLL is a major contribution for LLNs but it is a proactive approach and has standing cost of DAGs, and caters static sinks, source, and relaying nodes.
There exist many sink mobility strategies in literature that can be classified as random, predictable/deterministic and controlled mobility [4]. Researchers have done a lot of work and different algorithms have been proposed for sink mobility (single or multiple sinks) for even consumption of energy in wireless sensor networks [3, 9]. In LURP (Local Update-based Routing Protocol), when sink moves it just needs to send its location information only to local area rather than entire network [2]. Various other mechanisms are proposed where sinks need to update about their location information other nodes in network where to send future data. It is not suitable for LLNs because sending location information frequently to network nodes will cause extra energy consumption and increase in network traffic.
MSPR (Mobile Sink based Routing Protocol) solves the hole problem but it involves controlled movement of a sink towards nodes having high energy, thus increases the network time [9]. Another work propose to predict QoS routing to mobile sinks; it needs mobility graphs to predict and pre-compute routing potentials and store it in network that require high memory, space and energy that is not suitable for LLNs [1].
Some work specifically in IETF proposed RPL is distributed and weighted moving strategy for sinks towards leaf nodes; it is autonomous mobility where the sink take decision to move [3]. An often used way to solve the problem is to formulate it as an integer linear programming (ILP) task. It has several drawbacks. First, it assumes a global knowledge of the topology, the solution is then calculated based on this global information; however, practically, such knowledge cannot usually be assumed.
Second, the ILP solution can only find the optimal choice out of a limited number of possibilities. It is costly and hard to repeat whenever a situation change, sink nodes repositioning is required. Finally, the ILP approach does not scale for networks with thousands of sensors [5]. Different algorithms have been proposed for positioning and mobility of sinks, like Global algorithm that calculates the position of sinks through mathematical model, 1-hop algorithm, clustering algorithms (k-mean). Some works propose use of data mules in case of mobile sinks but that is not suitable for LLNs as they do not consider energy, memory constrained network [8].
Hydro is a hybrid routing protocol for low power and lossy networks to meet the requirements of robust collection, point-to-point communication, and low footprint. In Hydro nodes form and maintain distributed DAGs that provide them with a set of default routes for communicating with border routers. These border routers maintain a global view of the network using topology reports received from each of the nodes, and subsequently install optimized point-to-point routes within the network [14]. Hydro is combination of collection based and point-to-point communication. The hybrid routing protocol presented in this work maintains DAGs according to mobility of sink whereas Hydro [14]
creates DAGs for the complete network. Ccontrary to all previous work, our work focuses on enhancing RPL to efficiently handle sink mobility with minimum energy expenditure.
III. NETWORKMODEL
In this section, the network model, assumptions and definitions regarding proposed protocol have been presented.
A wireless sensor network composed of static sensor nodes and mobile sinks have been considered in this work.
Network consists of N nodes that are distributed in a bi- dimensional grid. Nodes in the network have a limited initial energy and a fixed transmission range. The sinks are mobile and stay at a certain position for at least a certain duration of time T. At the end of this duration, they can change their locations. Sinks maintain the DAGs up till ‘x’ hop nodes instead of up till complete network to reduce the standing and maintenance cost. Nodes that have data to send and will start the sink discovery procedure only if they do not have a path to sink. Time period, for which the source will wait to get any reply before retransmission of route request is ‘t ’.
Since the energy spent in the communication is the most dominant, only the energy consumption for transmitting and receiving data is considered. ‘σ’ is the number of hops up till
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
which source is transmitting request, ‘η’ is the number of nodes at each hop distance, is the cost of single transmission, = w(e)c(e). The transmission cost over an edge ‘e’ depends on two factors: the unit cost of the link for transmitting data from node ‘u’ to ‘v’, and the amount of data to be transmitted. The latter factor is simply w(e). In practice, cost per unit data depends not only on the Euclidian distance between the two nodes and the physical layer technology employed, but also on the various networking overhead [13]. β is the number of neighbor nodes around each node in network (assuming it to be same for all nodes), α is the number of nodes that have already received requests, then the total cost of transmission, for this proposed mechanism can be calculated as:
= (∑σ ) - α (1)
The above mentioned transmission cost will be much less than the cost required to broadcast the request for entire network.
Figure 1: Network topology
IV. PROPOSEDHYBRIDROUTINGPROTOCOL In this section, the operation of the proposed hybrid routing protocol for routing on Low power Lossy Network (LLN) containing mobile sinks has been explained. In most of practical scenarios of LLNs there exist mobile sinks (multiple sinks) that change their position timely, consequently changing the network topology. In this case nodes have to discover the sink that is closest to them.
In our network, we consider multiple sinks that are mobile and change their positions after an interval. These sinks maintain DAG as in RPL but size of this DAG ‘x’ is only few hops that depend on size of network, unlike RPL that can maintain DAG for complete network (N nodes).
Moreover, the maximum size of DAG’s in our case is set according to the speed of sink node. If the sink is highly mobile then it can use lower DAG values like 2-3 hops while in case of low mobility DAG’s for 6-7 hops can be maintained. If mobile sinks will maintain DAG for all nodes
then there will be more standing and maintenance cost as sinks will change position periodically/randomly. Therefore, rebuilding DAGs will be required accordingly. Likewise, during DAG rebuild phase, nodes can use stale routes causing packet drops, increased retransmissions and consequently will decrease network life time.
In our hybrid routing protocol, a node can immediately send data, if it is a member of active DAG (proactive approach). It will send the data to sink via preferred parents as in basic RPL mechanism, else it will broadcast route request (reactive approach) in the zone of σ-hop neighbors and will not broadcast it to entire network (value of σ depend on size of network). If there is sink in that zone (σ-hop area) or any node that is member of active DAG, it will send reply to source node. Sink will save the path for future communication. Otherwise, source will wait for certain interval of time ‘t ’ if it finds any nearest sink in this duration it will start transmission else after this interval it will increase the value of ‘σ’ (zone size), send route request again to σ-hop neighbors and will search for nearest sink.
This procedure will be repeated until the maximum number of retries imax. In case, if no sink is found up till maximum number of retries, route request will be broadcasted to entire network. By increasing the zone size the probability of finding the closest sink will increase while reducing the load on network, increasing efficiency and reducing the energy consumption. The flow chart of the sink discovery procedure has been presented in Figure 2.
In the remaining of this section, the two cases i.e., if a node is an active member of a DAG and if the node is not an active member of a DAG; are elaborated for finding a path to the sink.
Increment the retry
Source
Select Zone (σ)
Wait for interval
‘t ’
Send Reply to Source Member of active DAG
Sink/Member of active DAG found Send request up till σ-hop neighbors
Maximum retries
Send data to Sink
Broadcast to entire network No
No
Yes
Yes Initiate Route Request
Yes
No B
A
β=3
=4
C D
E
F G H
I
=2
=3
σ=3
α= 9 (for this topology)
Figure 2: Flow chart for sink discovery.
(1) (1)
(1) (2)
(2) (2)
(3)
S
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
A. CASE1: NODEISAMEMBEROFDAG
If the source node that has some data to send is itself member of active DAG, it will communicate according to basic RPL functionality and will send data to sink via preferred parents as shown in Figure 3. In this case routing is proactive in nature as the paths are already available to node in its routing table. This case is presented in Figure 3 where node A has data to send and it is a member of DAG.
Figure 3: Source node A is an active member of DAG communication with sink occurs via DAG links.
B. CASE2:NODEISNOTAMEMBEROFDAG In this case, the source node will broadcast the route request within a zone of to all of its σ-hop. Route request can be propagated within the zone using controlled flooding. If the sink or any active member of a DAG is found in this zone it will send reply to source. The intermediate nodes forwarding the reply to the source will maintain the state for future communication. In this way source can join the DAG temporarily as long as transmission continues. Any member node of DAG can use already maintained DAG links for forwarding data to the sink.
Multiple route replies from intermediate DAG member nodes can arrive at the source. In this case, the source can send data immediately after receiving the first reply.
Moreover, in order to decrease the replies DAG member nodes do not forward the route request to the sink. Also, overhearing is used by intermediate nodes to stop the further propagation of route request/reply messages once a reply has been heard from neighboring nodes.
If source does not find the sink from its first route request in the initial zone after a certain period t , it will increase the ‘σ’ thus increasing the zone size. The route request will be rebroadcasted in the bigger zone. The sink discovery will continue until a path to sink is found or maximum numbers of zone based route request have expired.
After maximum tries the node will broadcast in the complete network for sink discovery.
Figure 4: Source node A broadcast route request to its 3- hop neighbors and found member of active DAG that sent
back path to sink via intermediate nodes.
Figure 4 shows the case where node A that is not a member of DAG initiates route request. The first response in this case will be from the closest DAG member node E. For this network topology, dissemination of Route Request (RREQ), packet type, intended receivers and their actions have been listed in Table 1.
TABLE I: Sink Discovery message sent by node A Sender Packet Receiver Action
A RREQ B,C,D A initiates RREQ
B RREQ A,D,E B Forwards RREQ
& A,D drop it C Fwd
RREQ
A,D,F C Forwards RREQ
& A,D drop it D Fwd
RREQ B,C,F D Forwards RREQ
& B,C drop it E Fwd
RREQ B,H, DAG
members B drops it F Fwd
RREQ C,D,G G will not forward it & C,D drop it
In the proposed hybrid routing protocol for ROLL, the number of transmissions are reduced from entire network to only σ -hop neighbors. It will also reduce the network load in terms of control message traffic. Maintaining DAGs only up till few hops will reduce the standing cost of DAGs in huge networks. It will also reduce the DAG building time and cost as whenever sink will change its position it will build a small DAG.
V. CONCLUSIONANDFUTUREWORK In this paper, we have proposed an enhancement to RPL to efficiently support mobile sinks in the network. We have used hybrid routing protocol i.e., a combination of proactive and reactive approaches. Theoretically, our enhancement efficiently reduces the number of transmissions, network load, maintenance and standing cost of DAGs. In our future S
Source node (2)
(3)
B
(2) (1) (1)
A D C
(1)
(2)
S (1)
(1)
(1) (2)
(2) (2)
(3)
B E
A
C D
G F H
Source Node
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57
work, we will simulate the performance of this protocol for the selection of appropriate parameters such as zone size and frequency of sink messages for DAG establishment.
REFERENCES
[1] Branislav Kusy, HyungJune Lee, Martin Wicke, Nikola Milosavljevic, and Leonidas Guibas,
“Predictive QoS Routing to Mobile Sinks in Wireless Sensor Networks”,in IPSN’09, April 13- 16, 2009, San Francisco, CA, USA.
[2] Guojun Wang, Tian Wang, Weijia Jia, Minyi Guo, Hsiao-Hwa Chen, Mohsen Guizani, “Local Update- Based Routing Protocol in Wireless Sensor Networks with Mobile Sink” in ICC 2007.
[3] Leila Ben Saad, Bernard Tourancheau, “Sinks Mobility Strategy in IPv6-based WSNs for Network Lifetime Improvement,” in "International Conference on New Technologies, Mobility and Security (NTMS), Paris : France (2011)"
[4] T. T. Truong, K. N. Brown,C. J. Sreenan, “Using Mobile Sinks in Wireless Sensor Networks to Improve Building Emergency Response” Mobile &
Internet Systems Laboratory and Cork Constraint Computation Centre, Department of Computer Science, University College Cork, Ireland., 2010 [5] Zolt´an Vincze, Rolland Vida, Attila Vid´acs,
“Deploying Multiple Sinks in Multi-hop Wireless Sensor Networks”, in “IEEE International Conference on pervasive Services”, 2007.
[6] Lei Shi, Baoxian Zhang, Kui Huang, Jian Ma, “An Efficient Data-Driven Routing Protocol for Wireless Sensor Networks with Mobile Sinks” in IEEE ICC 2011.
[7] J. Luo and J.-P. Hubaux, “Joint mobility and routing for lifetime elongation in wireless sensor networks,”
In Proceedings 24th Annual Joint Conference of the IEEE Computer and Communications Societies INFOCOM, 2005.
[8] R. C. Shah, S. Roy, S. Jain, and W. Brunette, “Data mules: Modeling a three-tier architecture for sparse sensor networks,” in IEEE International Workshop on Sensor Network Protocols and Applications SNPA, 2003, pp. 30–41.
[9] Nazir B, Hasbullah H, “Mobile Sink based Routing Protocol (MSRP) for Prolonging Network Lifetime in Clustered Wireless Sensor Network”, in International Conference on Computer Applications and Industrial Electronics (ICCAIE), 2010
[10] Thomas Watteyne, Kris Pister, Dominique Barthel, Mischa Dohler, Isabelle Auge-Blum,
“Implementation of Gradient Routing in Wireless Sensor Networks”, in IEEE "GLOBECOM" 2009.
[11] P. Thubert, T. Watteyne, Z. Shelby, and D. Barthel,
“LLN Routing Fundamentals,” IETF ROLL, IETF Internet-Draft, 9 April 2009, draftthubert-roll- fundamentals-01
[12] R. D. Team, “RPL: Routing Protocol for Low Power and Lossy Networks,” IETF ROLL WG, IETF Internet-Draft, 4 February 2009, draft-ietf- roll-rpl-00
[13] Hong Luo, Jun Luo, Yonghe Liu, Sajal K. Das,
“Routing Correlated Data with Fusion Cost in Wireless Sensor Networks”, Center for Research in Wireless Mobility and Networking (CReWMaN), Dept. of Computer Science and Engineering The University of Texas at Arlington, 2006.
[14] Stephen Dawson-Haggerty, Arsalan Tavakoli, and David Culler, “Hydro: A Hybrid Routing Protocol for Low-Power and Lossy Networks”,in “First IEEE International Conference on Smart Grid Communication (SmartGridComm)” , 2010.
