Sage Journals: Discover world-class research

Abstract

In mobile sensor networks, a variety of dynamic environmental conditions affect performance. Node movement caused by the network environment or by mobile entities makes the sensors particularly vulnerable to route failures, which in turn affects the efficiency and reliability of these networks. Therefore, mobility is an important factor in the design of a routing protocol for mobile sensor networks. In this paper, we propose a mobility-aware efficient routing called MAER, in which sensor nodes make use of mobile information to select the most appropriate routing behavior. The proposed method integrates proactive and reactive routing components efficiently using a sink cluster that consists of underlying multiple static or slow sensor nodes. The cluster provides the stable paths between less mobile entities efficiently. Our scheme also uses mobile information to evaluate and select alternative paths during a route discovery process, thus allowing sensor nodes dynamically to adapt to varying mobile networks. We evaluate the performance of MAER using a simulation by comparing it to the most popular standard for WSN, AODV. The results of the simulation show that our scheme outperforms AODV in mixed mobile sensor networks.

1. Introduction

Mobility sensor networks (MSNs) are increasingly emerging in various application domains, from environmental monitoring to intelligent industrial automation. In MSNs, the energy efficiency during routing operations has been a primary metric because typical sensor nodes have constrained battery power [1]. However, the mobility that results from network environmental influences (e.g., wind and water) or from mobile objects (e.g., human, animal, robot, and vehicles) can degrade the energy efficiency of sensors significantly [2]. Also, as mobility increases, routing schemes are affected in different ways. In proactive schemes such as DSDV [3], the number of control messages increases dramatically to maintain the route before the link breaks regardless of whether data is being transmitted. On the other hand, in reactive schemes such as AODV [4], the sensor nodes discover the route to the destination only if they are needed. These schemes can also reduce the control overhead compared to proactive approaches. However, more frequent changes of the topology can lead to a failure of the discovery process even under a reactive scheme. Thus, we need to design a more efficient and robust routing scheme suitable for MSNs.

We focus on a hybrid approach that relies on mobility information and assumes that each sensor has different mobility information in a mixed sensor network consisting of static and mobile nodes although all sensors have the same mobility model. Most hybrid approaches concentrate on traffic loads considering the impact of the locality. However, in highly mobile sensor networks, the impact of mobility is more important than the benefits of the locality because most undelivered messages are caused by broken links due to node mobility, and the message loss can lead to numerous control messages from frequent route-maintenance and repetitive route-discovery attempts. In order to reduce the control overhead, our approach utilizes a stable path that is established between less mobile entities through the use of mobility information.

In this paper, we propose a mobility-aware efficient routing scheme called MAER, in which sensor nodes make use of their mobile information to select the most appropriate routing behavior and the best path among candidates. This represents a new integrated approach which includes both proactive and reactive strategies and hence is designed to work efficiently under varying mobile networks. The proposed routing scheme is based on a sink cluster. It takes into account the mobile status of each sensor node during clustering. A cluster consists of a spanning tree with irregular boundaries which relies on the number of static or slow nodes, unlike a traditional cluster, the size of which is the maximum number of hops from a cluster head. This modification lowers the cost of MAER by minimizing reconstructions of clusters. In particular, it adapts to varying mobile sensor networks by shrinking or expanding a cluster. Slow nodes in the cluster perform proactive routing by updating and recovering the routes within the cluster. Meanwhile, mobile nodes that do not participate in the cluster perform the reactive routing part. Furthermore, MAER uses an improved mobility-aware query control mechanism based on a sink cluster.

The rest of this paper is organized as follows. Section 2 addresses related works. Section 3 introduces the sink cluster that is established between less mobile entities for mobile sensor networks. The proposed mobility-aware efficient routing protocol is then given. Section 4 presents the simulation and experimental results. Finally, Section 5 summarizes this work.

2. Related Works

Routing protocols are classified into two categories: proactive (e.g., DSDV [3], OLSR [5], SPIN [6], and OSPF [7]) and reactive (e.g., AODV [4], DSR [8], LAR [9], and directed diffusion [10]). In proactive scheme, each node propagates control messages to maintain fresh entries in the routing table when the network topology changes. For example, in OSPF [7], sensors maintain routes proactively by depending on soft timers to detect a link failure. If a neighbor entry in route table is not periodically refreshed by a HELLO message, the entry is invalidated. Meanwhile, in reactive schemes, nodes send control messages to find the path to the destination only if there is data to send. The most popular standard for WSN is the IEEE 802.15.4 ZigBee standard, where a ZigBee network layer uses an ad hoc on-demand distance vector (AODV) routing [4]. In AODV, if there is no cached entry in the routing table, the source node initiates a route discovery process by broadcasting a route request (RREQ) message, which is rebroadcasted by other nodes until it reaches its destination. The destination node then responds via a route-reply (RREP) message which is sent back to the source node via a unicast reply mechanism. Directed diffusion [10] is another reactive routing scheme for WSNs. The sink propagates an interest message when it needs to collect data from sensor nodes. A proactive scheme can result in better performance with static networks in terms of latency because the routing information is maintained at all times. In contrast, a reactive scheme can perform more efficiently than a proactive scheme when there is greater mobility.

Hybrid schemes which combine proactive and reactive schemes have also been proposed. Examples include ZRP [11], EAGER [12], MSA [13], and ARPM [14]. The Zone Routing Protocol (ZRP) [11], in which each node has its own proactive zone with a proactive scheme performed within each zone, was the first hybrid routing scheme. Routing between nodes in different zones is performed by a reactive routing scheme. In EAGER [12], the network is partitioned into disjointed proactive cells in which each node utilizes a proactive scheme for intracell routings and reactive routing for intercell routings. The optimal cell size and transmission range are obtained analytically. In MSA [13], the authors propose a framework to select the best routing strategy given the mobility of the source and destination. They incorporate existing routing protocols into the framework. In contrast, ARPM [14] redesigns a hybrid protocol by integrating DSDV and AODV as a proactive and a reactive scheme, respectively. In ARPM, each node utilizes a different type of routing depending on the node's mobility.

The proposed MAER protocol differs from traditional zone- or cell-based adaptive schemes in terms of its network organization. In MAER, a cluster has a spanning tree with irregular boundaries made up of a number of less mobile entities so as to provide a stable path. The cluster in MAER adapt to varying mobile sensor networks by shrinking or expanding.

3. MAER: Mobility-Aware Efficient Routing for Mobile Sensor Networks

In this section, we present MAER, a mobility-aware efficient routing scheme for mobile sensor networks. First, we introduce the concept of a sink cluster in a mobile sensor network, after which we describe how MAER works in varying mobile sensor networks.

3.1. Sink Cluster

We take into consideration a network with N randomly dispersed mobile sensor nodes ( ${MS}_{i}$ , $0 \leq i \leq N$ ) and a sink node. We assume that all of the nodes have the same wireless transmission range r. Two nodes are considered neighbors if they are within the transmission range of one another. The nodes are moving randomly in different directions at different speeds. Each ${MS}_{i}$ contains the mobility information of the speed, which is measured at the node. To handle link failures and provide stable paths efficiently, MAER maintains a sink cluster rooted at the sink. Sensor nodes decide to join or leave a sink cluster based on their own mobile information relative to that of other members of the cluster.

A cluster has a spanning tree formed by slow sensor nodes with low levels of mobility (as characterized by, for instance, slow speeds and large pause times) under a given threshold. Let us consider a cluster called sink cluster (SC). It is formed by associating the sink with multiple slow nodes of height h. SC is composed of SCMs and a sink where SCM is a sink cluster member. The SCMs exploit a proactive routing protocol while also playing an intermediary role in efficient route discovery mechanisms, as described in the next subsection. We denote a set of nodes which can reach the sink in k hops as ${SC}_{k}$ ( $0 \leq k \leq h$ ). Accordingly, the sink node belongs to ${SC}_{0}$ .

The tree organization of an SC is initiated by the sink. The sink creates the cluster by periodically sending an advertisement broadcast message. A sensor node that receives the advertisement message within a single hop sends a join message to the sink if its degree of mobility drops below a given threshold $λ_{x}$ . In response to the join message, an acknowledgement message is sent from the sender of the advertisement message. Upon the reception of the acknowledgement message, the sensor node becomes the SCM node and registers the sender of the message as a parent node with a distance vector from the sink. Consequently, all of the neighbors that have mobility less than $λ_{x}$ join the cluster as an SC₁ node. Also, each SCM periodically sends advertisement broadcast messages during every interval $T_{a}$ , as our objective is to group all slow nodes for a more stable path. In this way, a sensor node joins ${SC}_{k}$ and becomes an SCM if the sensor node receives an advertisement message from an SCM in ${SC}_{k - 1}$ within a single hop and if the node's mobility is below a given threshold $λ_{x}$ . SCMs can also change their own parent node if the distance vector from other advertisement messages is less than their current distance vector. When the mobility of a SCM exceeds the threshold $λ_{y}$ , the node leaves the sink cluster by sending a leave message to both its parent and child nodes. If its parent node is no longer a SCM, the child node also leaves the sink cluster. Figures 1(a) and 1(b) illustrate mobile sensor networks and an example of a sink cluster when $h = 2$ , respectively.

Figure 1

(a) Mobile sensor networks and (b) a sink cluster for $h = 2$ .

This approach helps to minimize clustering overhead because the SC is composed of relatively slow nodes. In addition, the sink cluster topology is adaptive to varying networks. The cluster grows automatically when static or slow nodes are greater in number in the network and shrinks if more sensor nodes are moving faster, as shown in Figure 2. Furthermore, the sink cluster enables MAER to provide more efficient routing by integrating proactive and reactive routing schemes, as described in the next subsection.

Figure 2

The (a) expansion and (b) shrinking of a sink cluster according to the degree of node mobility.

3.2. Integrating of Proactive and Reactive Routing Components

In this subsection, we extend the discussion to the area outside of the sink cluster and present the details of the key design of integration of the reactive routing component based on the sink cluster. The SCM nodes perform proactive routing within the cluster infrastructure while the other mobile sensors use the reactive routing routine. The goal of reactive routing here is efficiently to find alternative stable paths for mobile nodes that do not belong to the cluster.

Conventional reactive schemes typically use a rebroadcast mechanism to accomplish route discovery, where every node broadcasts upon receiving a route request (RREQ) message for the first time. The rebroadcast mechanism, however, can lead to high channel contention and collisions, often known as the rebroadcast storm problem [15]. In MAER, because the SCM nodes already have a destination route, they stop rebroadcasting when a RREQ message is received. Instead, the SCM nodes convert the broadcast-RREQ message into a unicast-RREQ message and forward the converted message to their parent SCM node. With the help of the query conversion mechanism, MAER becomes more efficient than the conventional route discovery process.

We also enhance the route discovery process by the mobility factor for path selection. In MAER, each ${MS}_{i}$ has a weight value, denoted as $ϕ_{i}$ , assigned as a cost according to its own mobile level. The mobility factor is the cumulative sum of the weight values of all intermediate nodes that form the path. This approach requires the modification of the routing table so that it contains the mobility factor for the paths. When a RREQ message arrives, each node adds its weight value to the mobility factor field of the message and the node updates its routing table. This procedure is repeated until the RREQ message reaches its destination. The cumulative mobility factor included in the RREQ message is recorded in the destination's route table. In addition, the expected mobility factor for a path with l hops can be calculated by dividing the factor by the hop count. Note that a lower mobility factor indicates that there are fewer mobile entities among the intermediate nodes in the path, whereas a higher mobility factor implies the opposite. As a result, the path with the minimum mobility factor is utilized during the route discovery process instead of the shortest path. Although the path may not the shortest, it can be a more stable path when established between less mobile entities. Therefore, when RREQ messages arrive, each node has to update the route table if the mobility factor in the RREQ message is lower than that in the route table. The SCM nodes, however, have to forward the unicast RREQ to their parent node after updating the routing table entry. When the RREQ reaches its destination, a route reply (RREP) message is not immediately sent to the source node. To construct a stable route, the RREP message is delayed for an acceptable time. However, this lazy reply mechanism can lead to long setup times when discovering routes with lower mobility factors.

To illustrate how MAER routing works, Figure 3 shows an example with a sink cluster. When MS₁ has sensed data to send to the sink but has no existing route to the sink, it initiates a route discovery process by broadcasting a RREQ message that contains its weight value $ϕ_{1}$ of 3 for the mobility factor. MS₂ and MS₃, upon receiving the RREQ for the first time, add their weight values to the mobility factor in an accumulative manner and then rebroadcast the message. Then, MS₄, MS₅, and MS₆ repeat this rebroadcast procedure. Nodes MS₁, MS₂, MS₃, and MS₄ can receive several RREQs, but they do not forward it again because they have already forwarded the RREQ once. Instead, they compare the mobility factor to their current mobility factor in the route table entry in order to determine better paths for every RREQ arrival time. Because MS₅, MS₆, and MS₇ are SCM nodes that participate in the sink cluster, they convert the RREQ into the unicast type and forward it to the parent nodes MS₈, MS₉, and MS₉, respectively; specifically, MS₅ does not convert the RREQ message received from MS₂ to the parent node MS₈ because the mobility factor of $(ϕ_{1} + ϕ_{2})$ is higher than the current mobility factor of $(ϕ_{1} + ϕ_{3})$ in the route table. Likewise, MS₆ does not forward the RREQ message received from MS₄ again. MS₉ also does not send the message from MS₇ to its parent node again. When the sink receives the RREQ, the sink initiates the lazy reply process. After waiting time $T_{s}$ , the destination node creates the RREP and sends it back. Although the RREQ from MS₈ arrives first, the sink selects MS₉ for the next node toward the source node.

Figure 3

An example of our mobility-aware efficient routing.

4. Performance Evaluation

In this section, we evaluate the performance of MAER. We compare the proposed mechanism of MAER with one of most popular standard routing protocols for mobile sensor networks, AODV. We also use two different advertisement intervals ( $T_{a} = 0.5$ and 2) in MAER. For join and leave messages, the thresholds $λ_{x}$ and $λ_{y}$ are given values of 4 m/s and 8 m/s, respectively. We assigned a weight value to each of four levels with a preliminary cost of 4, 3, 2, or 1 according to the mobility threshold, which have values of 4 m/s, 8 m/s, and 16 m/s. In all simulations, 100 sensor nodes are randomly deployed in a square area with a size of 500 m × 500 m. After the initial placement, nodes move continuously according to the RDMM [16] model; every node keeps moving in a random direction at a random speed during every epoch. Each node has the same transmit power of coverage of 100 m. We also assume that the channels are free of errors and collisions. Each data is averaged over 10 simulation runs with a different seed. Based on the parameters described above, we consider two different mobility scenarios: (i) a uniform case in which all nodes keep moving continuously according to the same RDMM model and (ii) a mixed case where the nodes are categorized as either static nodes or mobile nodes according to their RDMM behavior.

We consider the packet delivery rate and the control overhead in the following two-part metric: (1) the ratio of the total number of packets that the sink receives to the total number of packets that the sensor nodes send and (2) the number of control bytes for reception and transmission. We evaluated this metric according to various maximum node speeds and numbers of static nodes for each model. Table 1 shows some of the important simulation parameters.

Table 1

Parameters used in the simulation.

Notation	Description
Size of field	500 × 500 m²
Distribution of nodes	Random distribution
Number of nodes (N)	100
Transmission range (r)	100
Data packet size	256 bytes
Mobility model	RDMM (Random direction mobility model)
Traffic load	Constant bit rate
Propagation model	Free space model

Figure 4 shows a comparison of the average packet delivery rate with respect to different degrees of mobility in the uniform mobility case. In all schemes, the packet delivery rate decreases as the maximum speed of the nodes increases from 10 m/s to 40 m/s because the broken links caused by the mobility characteristic degrade the packet delivery ratio; specifically, we found that the conventional AODV scheme has increased difficulty when dealing with high node mobility. MAER improves the packet delivery ratio by about 5% compared to AODV. As expected, MAER can be improved with a shorter interval in terms of the packet delivery rate, as the advertisement messages stabilize the clusters. Figure 5 shows the number of control overhead bytes needed to achieve the packet delivery. The control overhead of AODV is more significant when the mobility of the nodes increases. Due to its frequent messages, MAER usually generated more control traffic than AODV when the maximum speed equaled or exceeded 10 m/s. The control overhead of MAER did not scale linearly with high mobility.

Figure 4

The packet delivery rate according to the mobility of node.

Figure 5

The control overhead according to the mobility of node.

Figure 6 shows the packet delivery rate for different number of static nodes in the mixed case (i.e., a mixed MSN consisting of both static and mobile nodes). The packet delivery rate of MAER is better than that of AODV. In particular, we achieved a significantly higher packet delivery rate at a lower cost in the mixed case. Moreover, MAER yields better results for high mobility. This improvement is attributed to the static nodes used to provide stable paths from among alternatives regardless of the maximum speeds of mobile node.

Figure 6

The packet delivery rate according to the number of static nodes.

Figure 7 shows the control overhead with various static nodes. Here, AODV appears to perform best. However, when taking into account the packet delivery ratio, as shown in Figure 6, AODV shows the worst result. As the number of static nodes increases, the difference of control bytes between AODV and MAER becomes smaller. This is largely due to the fact that they adapt dynamically to network conditions through an efficient discovery process based on the sink cluster.

Figure 7

The control overhead according to the number of static nodes.

For a fair comparison, we measured the number of control bytes per data packet delivered. Figure 8 shows the control overhead per successful data transmission according to the traffic load. The simulation results show that MAER outperforms AODV in all cases; specifically, when the traffic load is heavier (packet traffic rate ≤2), MAER with $T_{a} = 0.5$ generates relatively less control overhead compared to the case when $T_{a} = 2$ . This indicates that the effect of updating the cluster becomes less efficient under a light traffic load.

Figure 8

The control overhead per successful data transmission.

5. Conclusions

We have presented a mobility-aware routing scheme for mobile sensor networks, called MAER. The goal of MAER is to adapt to mobile sensor networks by taking into consideration the node's level of mobility. Our scheme exploits a sink cluster formed by slow nodes with low mobility to establish a stable path between less mobile entities. It also provides stable paths in an efficient manner using a query control mechanism based on the mobility factor. Simulation results show that our scheme outperforms AODV in terms of the packet delivery rate and control overhead in mixed mobile sensor networks.

References

Lian

Naik

Agnew

G. B.

Data capacity improvement of wireless sensor networks using non-uniform sensor distribution

International Journal of Distributed Sensor Networks 2006 2 2 121 145

2-s2.0-34548851055

10.1080/15501320500201276

Zhang

Trappe

Managing the mobility of a mobile sensor network using network dynamics

IEEE Transactions on Parallel and Distributed Systems 2008 19 1 106 120

2-s2.0-37149006099

10.1109/TPDS.2007.1113

Perkins

C. E.

Bhagwat

Highly dynamic destination sequenced distance vector routing (DSDV) for mobile computers

Proceedings of the ACM Conference on Communications Architectures, Protocols and Applications (SIGCOMM ′94)

1994

234 244

Perkins

Belding-Royer

Das

Ad hoc on-demand distance vector(AODV) routing

2003 3561

IETF MANET Working Group

Kulik

Heinzelman

Balakrishnan

Negotiation-based protocols for disseminating information in wireless sensor networks

Wireless Networks 2002 8 2-3 169 185

2-s2.0-0036499227

10.1023/A:1013715909417

Clausen

T. H.

Jacquet

RFC3626, Internet Engineering Task Force (IETF), 2003, http://www.ietf.org/rfc/rfc3626.txt

Moy

OSPF version 2 RFC, 2328, 1998

Johnson

Maltz

Y. C.

The dynamic source routing protocol for mobile ad hoc networks (DSR)

2004

IETF MANET Working Group

Y.-B.

Vaidya

N. H.

Location-aided routing (lar) in mobile ad hoc networks

1998

College Station, Tex, USA

Department of Computer Science, Texas A&M University

10.

Intanagonwiwat

Govindan

Estrin

Heidemann

Silva

Directed diffusion for wireless sensor networking

IEEE/ACM Transactions on Networking 2003 11 1 2 16

2-s2.0-0037295692

10.1109/TNET.2002.808417

11.

Haas

Z. J.

Pearlman

M. R.

The Zone Routing Protocol (ZRP) for ad hoc networks

IETF

Internet Draft, draft-zone-routing-protocol-02.txt, 1999

12.

Zhao

Tong

Counsil

Energy-aware adaptive routing for large-scale ad hoc networks: protocol and performance analysis

IEEE Transactions on Mobile Computing 2007 6 9 1048 1059

2-s2.0-34547466055

10.1109/TMC.2007.70716

13.

Bamis

Boukerche

Chatzigiannakis

Nikoletseas

A mobility aware protocol synthesis for efficient routing in ad hoc mobile networks

Computer Networks 2008 52 1 130 154

2-s2.0-36049023817

10.1016/j.comnet.2007.09.023

14.

Seba

H. L.

ARPM: an adaptive routing protocol for MANETs

Proceedings of the International Conference on Pervasive Services (ICPS ′06)

June 2006

295 298

2-s2.0-33845956605

15.

Tseng

Chen

Sheu

The broadcast storm problem in a mobile ad hoc Network

Proceedings of the 5th ACM/IEEE Annual International Conference on Mobile Computing and Networks (MOBICOM ′99)

1999

151 162

16.

Royer

E. M.

Melliar-Smith

P. M.

Moser

L. E.

An analysis of the optimum node density for ad hoc mobile networks

Proceedings of the IEEE International Conference on Communications (ICC ′01)

June 2001

857 861

2-s2.0-0034858506