Wireless Sensor Network
Vol.09 No.01(2017), Article ID:73723,48 pages
10.4236/wsn.2017.91003

Location-Based Routing Protocols for Wireless Sensor Networks: A Survey

Arun Kumar1, Hnin Yu Shwe2, Kai Juan Wong3, Peter H. J. Chong4

1School of Electrical and Computer Engineering, National University of Singapore, Singapore

2School of Electrical and Electronics Engineering, Nanyang Technological University, Singapore

3Information and Communications Technology, Singapore Institute of Technology, Singapore

4Department of Electrical and Electronic Engineering, Auckland University of Technology, Auckland, New Zealand

Copyright © 2017 by authors and Scientific Research Publishing Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

Received: November 3, 2016; Accepted: January 20, 2017; Published: January 23, 2017

ABSTRACT

Recently, location-based routings in wireless sensor networks (WSNs) are attracting a lot of interest in the research community, especially because of its scalability. In location-based routing, the network size is scalable without increasing the signalling overhead as routing decisions are inherently localized. Here, each node is aware of its position in the network through some positioning device like GPS and uses this information in the routing mechanism. In this paper, we first discuss the basics of WSNs including the architecture of the network, energy consumption for the components of a typical sensor node, and draw a detailed picture of classification of location-based routing protocols. Then, we present a systematic and comprehensive taxonomy of location-based routing protocols, mostly for sensor networks. All the schemes are subsequently discussed in depth. Finally, we conclude the paper with some insights on potential research directions for location-based routing in WSNs.

Keywords:

Location-Based Protocol, Geographic Routing, Wireless Sensor Networks, Energy Conservation, Routing

1. Introduction

In recent years, location-based routing has emerged as the prominent area of research in the field of wireless sensor networks (WSNs). Sensor nodes may not have the internet protocol (IP) addresses; therefore, IP-based protocol cannot be used for the sensor networks. Building an efficient, scalable and simple protocol for WSN is very challenging due to limited resources and the dynamic nature of sensor networks. In location-based routing, the node does not need to make complex computations to find the next hop, as routing decisions are taken using the location information. Location-based protocols are very efficient in terms of routing data packet as they take the advantage of pure location information instead of global topology information. This paper presents a survey and taxonomy of location-based routing for sensor networks.

In location-based routing, a node that has a packet to send (Source) adds a destination location (Sink) in each data packet. Intermediate nodes in the path receive this packet and send it to next one-hop neighbours which are geographically closest to the destination. The process is continued until the data packets are received by the destination node. In location-based routing, the state required to be maintained in each node is minimum, because of the locality. It has low communication overhead because advertisements of routing tables, like in traditional routing protocols, are not needed. Location-based routing thus does not require the establishment or maintenance of routes. Therefore, Location-based routing conserves both energy and bandwidth since route request and state propagation are not required after one-hop distance.

Location-based routing uses the location information for nodes to provide higher efficiency and scalability. It requires three facts: first, each node in the network must know its own location information by GPS or by any other methods [1] [2] [3] [4] . Second, each node must be aware of its neighbour node’s location which is one-hop away from it. Third, the source must be aware of the location of destination node.

Location-based routing requires the correct location information, which can be obtained using some localization mechanism. Location information is essential for many wireless network applications, so it is expected that each wireless sensor node in the network will be equipped with some localization devices. Several techniques [1] [3] [4] exist for location sensing based on proximity or triangulation using radio signals, acoustic signals, or infrared. These techniques differ in their localization granularity, range, deployment complexity and cost. Most of the location mechanisms utilize the flooding [5] to spread the sink’s location up to all other nodes, which is undesirable for the large-scale WSNs, especially when the multiple mobile sinks and sources exist.

Location-based routing usually uses a greedy forwarding mechanism to forward a data packet from source to destination. Greedy approach forwards packets to the neighbour, which is closest to the destination. It assumes that the network is sufficiently dense; each node has its own accurate location information, its neighbours’ locations, and high link reliability. Dense sensor deployment [6] and reasonably accurate location information may be acceptable in some WSN applications. But the high link reliability is not acceptable in any realistic deployment. Because recent studies [7] [8] show that wireless links can be highly unreliable and have to deal with the higher-layer protocols.

Many forwarding strategies [9] are proposed to improve the performance of geographic routing. These forwarding strategies can be broadly divided into two categories: distance-based and reception-based. While the nodes need to know only the distance to their neighbours in distance-based strategy, the nodes also know the packet reception rates of their neighbours in reception-based strategy. Both strategies use the greedy-like forwarding to choose the next hop in the forwarding process.

In order to understand localtion based routing in WSN, we begin with an overview on WSN. The overview includes common architectures of sensor networks, available protocols and application areas in WSN. We then provide a taxonomy of localtion-based routing protocols for WSN. A table comparing different location-based routing protocols is given at the end of this paper. In addition, we discuss the available ad-hoc routings in WSN. To the best of our knowledge, there is no paper to give a survey on location-based routing for WSNs. With this article, readers can have a more thorough and delicate understanding of location-based routing for WSNs and the research trend in this area.

2. Wireless Sensor Networks

2.1. Architecture of WSNs

WSNs have attracted many researchers in this field of research in the past few years. The advancement in the field of micro electro mechanical systems (MEMS) has open the way to develop low-cost, low-power, multi-functional, tiny sensor nodes [10] [11] [12] . These tiny nodes are capable to sense the environment, perform data processing and having the capability to communicate with other nodes in the network over short distances. A typical architecture of WSN is shown in Figure 1.

WSN consists of at least one sink node (or base station) and a (large) number of sensor nodes deployed in the network field. Sensor nodes in the field sense and collect raw data from the environment to do some local processing, communicate with each other to perform aggregation in necessary, and then route the aggregated data to the sink. Sink or base station serves as a destination node for the sensor nodes. User can access the data from the sink by internet or satellite.

Figure 1. Architecture of wireless sensor network.

A large-scale WSN consists of thousands of sensor nodes deployed according to the application [13] [14] . Wireless sensor nodes are small devices that have three basic components. First, a sensing device for data acquisition from the physical surrounding environment. Second, a processing unit for local data processing and storage. Third, a wireless communication device for data transmission. An archi- tecture of typical wireless sensor node [15] [16] and a berkeley Mote (Real-life sensor node) [17] is shown in Figure 2 and Figure 3 respectively.

These sensor nodes have several resource constraints such as limited memory, battery power, signal processing, computation and communication capabilities. These nodes are mainly deployed in remote areas and intended to work for WSN research interest. Many research prototype sensor nodes such as UCB motes [18] , uAMPS [19] [20] , MICA [21] and PC104 [22] have been designed many years so lifetime extension of sensor networks play an important role in and manufactured. Energy efficient MAC [23] [24] [25] , and different routing schemes are implemented and evaluated for the real life application of WSNs.

WSNs require sensor nodes to communicate with each other frequently depending on the application, making data dissemination a challenging task in large networks. During data dissemination in WSNs, data transmission consumes more energy than data processing in a sensor node. The energy required to transmit a single bit is comparable to the amount required to process a few

Figure 2. Architecture of a typical sensor node.

Figure 3. Berkeley mote [17] .

thousands operations in a typical sensor node [26] . Sensing subsystem energy consumption depends on the sensor type. In some cases, it is negligible when compared with processing and transmission energy. But on the other hand, data sensing may be comparable to, or even greater than, the energy needed for data transmission.

Mainly, energy-saving techniques focus on network subsystem and sensing subsystem. In networking subsystem, energy management is taken into account in the operations of each single node, as well as in the design of networking protocols. In sensing subsystem, techniques are used to reduce the amount or frequency of energy-expensive samples. The lifetime of the sensor network can be prolonged by applying different energy conservation techniques. However, the main energy consumption components are CPU radio, even if they are idle. Therefore, different power management schemes are used to switch off the node components that are temporarily not necessary. Conserving the energy of the nodes can prolong the lifetime of the whole network.

Sensor networks can be broadly classified into two types; homogeneous and heterogeneous sensor networks. In homogeneous sensor network, all the sensor nodes are identical in terms of battery energy and hardware complexity. On the other hand, two or more different types of nodes with different battery energy and functionality are used in heterogeneous sensor network.

Sensor nodes do not have the IP address so, the queries are directed to a region containing a cluster of sensors rather than specific sensor addresses. We can say that sensor networks are predominantly data-centric rather than address-centric. Aggregation of the data is performed locally and a summary or analysis of the local data is prepared by an aggregator node within the cluster, thus reducing the communication bandwidth requirements. Dedicated routing protocol is required for dissemination of data packet through shortest path. Redundancy must be considered to avoid congestion when different nodes are sending and receiving the same information. However, redundancy must be exploited to ensure network reliability. Data dissemination can be query driven or based on continuous updates.

2.2. MAC for WSNs

In past few years, several medium access control (MAC) layer protocols were proposed to improve the performance of the sensor network. MAC protocols basically prolong the network life time by switching on and off the sensor node components like the radio transceiver. B-MAC [27] is a low power and flexible MAC protocol based on CSMA. It provides basic operations and interfaces help dynamically change the parameter of the protocol to compromise with the varying communication environment. B-MAC also provides two-directional interface for routing protocol and MAC protocol to communicate with each other by calibrating the parameter of the interface. It utilizes the sleep and wakeup technique to save the energy of the node. It does not support multicast and thus messages have to wait for another cycle to forward the data.

RMAC is an energy efficiency duty cycle MAC protocol for WSN. RMAC uses sleep period to send/receive data between nodes and forward control packet along the route during one duty cycle. The control packet helps the receiver to calculate the exact wakeup time. It uses data period to transmit PION packet instead of data and calculates to forward data packet to more than one node along the route in sleep mode. It does not support broadcast mode and bust data mode.

Z-MAC is a hybrid adaptive MAC protocol. The main idea is to make of CSMA as the foundation and TDMA as the hint for protocol. Based on the B-MAC operation, Z-MAC proposed a flexible and adaptive MAC with the data in the network. Z-MAC easily adapt with the changing content of the sensor network. It is suitable for the application with medium to high, two-hop contention. The drawback of Z-MAC is that many algorithms were needed to initialize and maintain the status of the network such as DRAND to assign node slot, TPSN to synchronize the global clock.

T-MAC is a contention-based MAC protocol for WSN which uses the duty cycle (alternatively active/sleep node) to increase the life of the nodes. It proposed an adaptive duty cycle by dynamically ending the active part of it. This can reduce the energy consumption on idle listening, while giving a constant and reasonable throughput.

S-MAC [28] utilized three novel techniques to reduce energy consumption and support self-configuration. Nodes periodically sleep to save the energy wasted by idle listening. Neighbouring nodes form virtual clusters auto-syn- chronize on sleep schedules. S-MAC utilizes the message passing technique to reduce contention latency for sensor-network applications that require store- and-forward processing as data moves through the network. S-MAC has better energy conserving properties compared to the IEEE 802.11. It also has the ability to trade-off between energy and latency according to traffic conditions.

2.3. Application of WSNs

A wireless sensor network is a wireless network consisting of spatially distributed autonomous devices with sensing, computation and wireless communication capabilities to cooperatively monitor physical or environmental conditions, such as temperature, sound, vibration, pressure, motion or pollutants at different locations. The development of the sensor network was originally motivated by military applications such as enemy tracking, tank and soldier surveillance and battle field surveillance. Today we can see a large number of application of WSNs, like industrial process monitoring and control [29] [30] , environment observation and habitat monitoring [31] [32] [33] , healthcare applications [34] [35] [36] , home automation [37] [38] [39] , traffic control [40] [41] and forecast systems [42] [43] [44] .

WSN applications typically involve the surveillance of physical phenomenon through the sampling of the environment situation. Accordingly, WSN applications can be classified as tracking and monitoring categories. Overall classification of sensor network applications is depicted in Figure 4.

Location-based routing plays a massive role in the military application, volcano monitoring, environment observation, traffic control, forecast system and so on. Location-based routing protocols are efficient for getting the information from a particular region. It is also very useful when the terrain is not accessible by human being like volcano monitoring. Many real life projects are running in the different parts of the world using the location-based routing in to consideration like Zebranet [45] , wildCENSE [46] , PinPtr [47] , CenWits [48] and volcanic monitoring [49] .

3. Ad-Hoc Routings

Many ad-hoc routing protocols were proposed to enhance the efficiency of ad-hoc network. Most well-known protocols are like DSR [50] , DSDV [51] , TORA [52] and AODV [53] . Both of Dynamic source routing (DSR) [50] and Ad-hoc on demand distance vector routing (AODV) [53] protocols flood the route request on-demand which help to save the bandwidth and also increase the battery power (not sending and receiving the message unnecessarily). Even if the link is broken, the AODV provides loop-free routes. On the other hand, temporally- ordered routing algorithm (TORA) [52] is from the family of “link reversal” algorithms. TORA is best to use in large, dense and mobile networks. TORA is an efficient and scalable protocol and shows a high degree of adaptively. Sensor networks require more energy and bandwidth saving than the Ad-hoc networks; and the communication in sensor networks is data-centric as opposed to address- centric in ad-hoc networks. And the communication in WSN is data-centric as opposed to address-centric in ad-hoc networks. Therefore the ad-hoc network

Figure 4. Overview of sensor network applications.

protocols are undesirable for sensor networks.

The few major differences between wireless sensor networks and ad-hoc networks are given below.

1) Sensor networks are mainly used to collect information while MANETs (Mobile Ad-hoc Networks) are designed for distributed computing rather than information gathering.

2) The number of sensor nodes in a sensor network can be several orders of magnitude higher than the nodes in an ad hoc network.

3) Sensor nodes are densely deployed.

4) Sensor nodes are prone to failures.

5) The topology of a sensor network changes very frequently.

6) Sensor nodes mainly use a broadcast communication paradigm, whereas most ad hoc networks use point-to-point communications.

7) Sensor nodes are limited in power, computational capacities and memory.

8) Unlike a node in ad-hoc networks, a node in sensor network may not have global Identification (ID) because of the large amount of overhead and large number of sensors.

9) Sensor nodes are much cheaper than nodes in ad hoc networks.

10) Usually, the data in sensor networks are bound either downstream to nodes from a sink or upstream to a sink from nodes, while in MANETs, the data flows are irregular.

4. Location-Based Protocols for WSNs

In this section, we survey the state-of-the-art location-based routing protocols for WSNs. Sensor nodes may not have the internet protocol (IP) addresses, therefore IP-based protocols cannot be used for the sensor networks. Building an efficient, scalable and simple protocol for WSN is very challenging due to limited resources and the dynamics nature of sensor network. In location-based routing, the node do not need to make complex computations to find the next hop, as routing decisions are taken using the location information. Location- based protocols are very efficient in terms of routing data packet as they take the advantage of pure location information instead of global topology information.

Location-based protocol uses the location information of nodes to provide higher efficiency and scalability. It requires three facts. First, each node in the network must know its own location information by GPS or by any other methods [1] [2] [3] . Second, each node must be aware of its neighbour nodes’ location, which are one-hop away from it. Third, the source node must be aware of the location of destination node. Location-based routing protocols can be mainly categories as shown in Figure 5.

Most of the location-based protocols are using the greedy algorithms to forward the packets to the destination. These algorithms only differ in how they handle the hole communication problem.

The earliest work in location-based is done by Finn and Gregory G. [54] in 1987. In this report, they proposed a flat routing mechanism called Cartesian

Figure 5. Categorization of location-based routing protocols.

routing. The drawback of the mechanism was its difficulty in determining an appropriate scope for the search.

Greedy perimeter stateless routing (GPSR) [55] uses a planar graph to avoid this problem. Planar graph is derived from the original network graph. The packet follows the perimeter of the planar graph to circumvent holes. The de- rived planar graph is much sparser than the original one, and the traffic concen- trates on the perimeter of the planar graph in perimeter mode. Thus, the nodes on the planar graph tend to be depleted quickly. In addition, nodes are assumed to operate in promiscuous listening mode and consequently consume energy.

Location aided routing (LAR) [56] , was proposed for the ad-hoc network. It uses the location information (location information obtained by GPS) to find the new route. By using the location information, the LAR limits the search in a smaller region called “request zone”. Limiting the search in the request zone significantly reduces the number of search message. The request zone is estimated by the previous information of the location and mobility pattern of the nodes. In case, the mobility pattern is not accurate, the request zone can be extended up to the whole network field.

The categorization of location-based routing is shown in Figure 5. To present the protocols in this paper we have divided the protocols in two sections, ac- cording to mobile or static nodes present in the network. Each protocol in these sections states which method they use to acquire the location information. In both sections, we survey in detail the protocols that fall below the location-based routing in WSN. Table 1 shows the detailed comparison among those location-based routing algorithms mentioned here. The properties chosen for comparison are mobility, energy-awareness, self-reconfiguration, negotiation, data aggregation, quality of service (QoS), state complexity, scalability, multipath, query-based, and GPS incorporation. Routing algorithms considering mobile nodes in the network are complex in nature as opposed to the static nodes. Due to limited energy of the tiny wireless sensor nodes, energy- awareness is an important characteristic for location-based routing protocols in WSN. As these protocols requires the location information, wireless sensor

Table 1.Comparison of Location-based Routing Protocols.

nodes must be equipped with some localization device like GPS or it will acruire the location information using other techniques [1] [3] [4] . Saclability and QoS are as important for location-based routing protocol as any other properties. Most of the location-based routing protocols are self-reconfigurable means, i.e., the network can rearrange and operate without any external help even when some nodes in the network are down (non-functional).

4.1. Network Topologies Using Mobile Nodes

This section focus on the location-based routing protocols which considers mobile nodes in network topologies. WSNs operations face serious issues if mobility is introduced in the network. In WSNs, mobile nodes have their advantages and disadvantages on diverse levels of the network operation. Sensor nodes mobility can be divided into two categories. First, sensor nodes may have limited mobility where only a handful of nodes are allowed to roam around the network to perform an exclusive task like a mobile sink nodes. Second, sensor nodes may have random mobility where all the nodes can roam round the network.

Advantages of introducing the mobility in the sensor network include enlargement of the scope of application (e.g., wild life monitoring, social activity monitoring, swarm bot actuated networks, etc.) and enhancement of the network operation as mobile nodes can lead to creation of different links for possible data transfer. And, if the mobility is limited then the mobile node can roam around through stationary nodes and gather the information sensed by static sensor nodes. The specific mobile node can also enhance the network connectivity by minimizing the congestion that can happen during network traffic flow.

In WSNs, mobility has its fair share of disadvantages. For example, if the mobility is limited to a special node(s), then those nodes can suffer from a bottleneck problem. Complex algorithms are required to estimate the optimum number and paths for the special node(s) to cover the entire deployed area of the network. And, if the mobility is random then the network topology changes become rapid and that affects the connectivity of the nodes. This results in the routing operations being affected as the links need to be rebuilt frequently leading to the increase in energy consumption of the nodes. Localization mechanism becomes a frequent operation resulting in unnecessary energy consumption of sensor nodes.

4.1.1. MECN and SMECN

Minimum energy communication network (MECN) [57] is a distributed position- based network protocol which focus is to minimize the energy consumption of the overall network. The protocol uses the low-power RF transceiver design for power management and also maintains a globally connected network in spite of possible module failure. The main focus of the protocol is on the self-configuration of the mobile node and energy consumption in the entire network. Protocol assumes that all the mobile node in the network having the similar antenna height to ignore the path loss problem. Protocol does not depend on a particular value of the path loss exponent n so it can be applied in various propagation environments. Protocol uses low power GPS by which each node gets its own instantaneous position in the network, but they do not get the position of the other node in the network. Protocol is showing good result when nodes are not mobile. One of the nodes from the network is uses as the information sink called “master-site” which will be located at the edge of the network field. MECN is using the concept the relaying the messages through the middle node, which consumes less power than sending the message directly. A three node example is shown for illustration of relaying concept in Figure 6.

Certain amount power is consumed while running the algorithm and processing the signal but it can be ignored since these are negligible compared to transmit and receive power. The relay region of the transmit-relay node pair (i, r) is shown in Figure 7.

Node i can compute the enclosure by taking the union of all relay regions that node i can reach. Through this MECN will find a sub-network, which will require less number of nodes as well as the less power for transmission between any two particular nodes. Enclosure of node i is depicted in Figure 8.

In this way, global minimum power paths are found by performing a localized search for each node considering its relay region without considering all the nodes in the network.

The protocol can be divided in to two phases:

Figure 6. Three collinear nodes A, B, C [57] .

Figure 7. Relay region of the transmit-relay node pair in MECN [57] .

Figure 8. Enclosure of node i [57] .

1) Search for enclosure: protocol uses the positions of a two-dimensional plane and constructs a sparse graph (enclosure graph), which consists of all the enclosures of each transmit node in the graph. This construction of sparse graph requires local computations in the nodes. It uses an auxiliary function called to update the relay graph. The enclose graph contains globally energy efficient optimal links.

2) Cost distribution: protocol finds optimal links on the enclosure graph. It applies distributed Bellman-Ford shortest path algorithm on the enclosure graph found in phase-1 with power consumption as the cost metric.

MECN is self-configuring in mobile scenarios and it can dynamically adapt to node failure or the deployment of new sensor. For power management, it uses low-power RF transceiver design. Protocol uses a local optimization technique which finds the minimum energy links and dynamically updates the link. Only local computation for updates is required and does not require much global information about the nodes. Interference between the nodes is reduced because the use of local information. Transmission of information is needed only over small distances because of the distributed protocol. But the main drawback for MECN is that it assumes every node can transmit to every other node which is not always possible in real time.

The small minimum energy communication network (SMECN) [58] is simply an extension of MECN. SMECN resolved the drawback of MECN by considering the possible obstacles between any pair of nodes. Similar to MECN, SMECN also assume that the network is fully connected. SMECN constructs a sub-network which is provably smaller (in terms of number of edges) than the sub-network constructed by MECN if broadcaster is able to send the entire broadcast message to all nodes in a circular region. In this way the number of hops required for transmission will be reduced. The results showed that SMECN uses less energy than MECN and the maintenance cost of the links is less. However, overhead of the algorithm is increased for finding the sub-network with smaller number of edges.

4.1.2. GAF

Geographical adaptive fidelity (GAF) [59] is an energy-aware location-based routing algorithm. It was primarily designed for ad-hoc networks, but it can also applicable for sensor networks. Algorithms turn on/off the nodes in the network to conserve energy and also keep a constant level of fidelity.

GAF creates a virtual grid for the covered area. Each node gets its current location through the GPS, which will use to associate itself with a point in virtual grid. Nodes that come under the same grid are considered equivalent in term of the cost of packet routing. After getting the location information, it is quiet not easy to find the equivalent nodes in an ad-hoc network because the nodes that are equivalent with some nodes may not be equivalent for the other nodes. The node equivalence problem is depicted in Figure 9 [59] . For communication between nodes 1 and 4, nodes 2 and 3 are equivalent, but for the communication between the node 1 and 5, only node 3 is acceptable.

Such equivalence is helpful to keep some nodes in the same grid in sleeping state in order to reduce the energy consumption. In this way, GAF substantially increases the network lifetime when the number of nodes increases. A simple example is depicted in Figure 10 [59] . The figure shows that, node 1 can reach any of nodes 2, 3 and 4 and nodes 2, 3 and 4 can reach node 5. Therefore, nodes 2, 3 and 4 are equivalent in the grid and thus two of them can sleep.

The virtual grid size is based on the radio range R. Suppose if the virtual grid is a square with r units as shown in Figure 10. The distance between the farthest nodes in any two adjacent grids, suppose as grid B and C in Figure 10, must not be greater than R in order to meet the definition of virtual grid. So we can compute r by:

(1)

or

Figure 9. Node equivalence problem [59] .

Figure 10. A simple example of virtual grid in GAF [59] .

(2)

Inside a grid, nodes balanced their loads by periodically changing their states from sleeping to active. GAF uses these three states:

1) Discovery―means finding out the other nodes in the same grid.

2) Active―means the node is participating in the routing.

3) Sleep―means the radio of the node is turned off.

The state transitions in GAF are depicted in Figure 11 [59] . Sleeping period of a node is application dependent and during the routing process, the related parameters are tuned. GAF is implemented for the non-mobility (GAF-basic) as well as mobility (GAF-mobility adaptation) of nodes. In the mobility scenario, each node in the grid computes its leaving time of grid and sends this to all its neighbours. Using this information, the sleeping nodes adjust their sleeping time accordingly in order to keep the routing fidelity. One of the sleeping nodes becomes active before the leaving time of the active node expires.

GAF always keep a node active in each region on its virtual grid to keep the network connected. Simulation results of the GAF showed that its performance is at least as well as the normal ad-hoc routing protocol in terms of latency and packet loss and overall increases the lifetime of the network by saving energy. GAF can also work as a hierarchical protocol where the clusters are based on geographic location. For each grid area, a representative node acts as the leader to transmit the data to other nodes. However, the leader node does not do any aggregation or fusion as in the case of other hierarchical protocols.

4.1.3. GEAR

Geographic and energy-aware routing (GEAR) algorithm [60] uses the geographic information while disseminating queries to appropriate regions. Disseminating information to a geographic region is a very useful primitive in

Figure 11. State transitions in GAF [59] .

many location-aware systems and especially sensor networks. GEAR uses energy aware and geographically informed neighbour selection heuristic to route a packet towards the target region instead of flooding the query or packet to the whole network. On the contrary, the interest is flooded in whole network in directed diffusion. Thus GEAR conserves more energy as compared to the directed diffusion. GEAR does not require the need for a location database and assumes the static sensor node in the network field. It is assumed that each node is attached with a GPS device to get its current location in the network and also assumed that each node knows its remaining energy level, and its neighbours location and remaining energy level through a simple neighbour hello protocol. The link in the protocol is assumed to be bi-directional.

In GEAR, each node has two types of cost parameter:

1) Estimated cost: it is a combination of residual energy and distance to destination.

2) Learned cost: it is a refinement of the cost that accounts for routing around holes in the network.

A hole in the routing path means that a node is not having any closer neighbour to the target region than itself. In case there is no hole in the path, the estimated cost is equal to the learned cost. Every time a packet reaches the destination the learned cost is propagated one hop back, thereby adjusting the route setup for next packet.

GEAR uses two phases:

Phase 1―forwarding packets towards the target region: when a node receives a packet, it checks that any neighbour node is closer to the target region than itself. If there is more than one, the nearest neighbour to the target region is selected as the next hop. If all neighbouring nodes are further away, it means there is a hole. In this case, one of the neighbours is picked to forward the packet based on the learning cost function. The choice will be updated according to the convergence of the learned cost during the delivery of packets.

Phase 2―forwarding the packets within the region: to diffuse the packet in the region, either recursive geographic forwarding or restricted flooding is used. Restricted flooding is good choice when the sensors are not densely deployed. In case of high-density network, recursive geographic flooding is more energy efficient than restricted flooding and the region is divided into four sub regions and four copies of the packet are created. This process (splitting and forwarding) continues until the region with only one node are left. An example is depicted in Figure 12 [60] .

GEAR does not depend on any particular type of MAC protocol. GEAR is compared with a similar non-energy aware routing protocol GPSR [55] which is one of the earlier works in geographic routing that uses planar graphs to solve the problem of holes. In GPSR, the packets follow the perimeter of the planar graph to find their route. GPSR has been designed for general mobile ad hoc networks and requires a location service to map locations and node identifiers. GEAR reduces energy consumption for the route setup and also performs better

Figure 12. Recursive geographic forwarding in GEAR [60] .

than GPSR in terms of packet delivery. The simulation results show that for an uneven traffic distribution, GEAR delivers 70% - 80% more packets than (GPSR) and for uniform traffic pairs, GEAR delivers 25% - 35% more packets than GPSR.

4.1.4. EELIR

Location-based energy efficient intersection routing (EELIR) [61] is location- based routing protocol for mobile sensor networks. EELIR assumes that each node in the network is aware of its own energy level, current location and the location of the sink node. It uses GPS for the localization. It is also assumed that all mobile sensor nodes are moving in a two-dimensional plane. The protocol works under three phases:

1) Start advertisement phase: the source node makes limited routing space and transmits the advertisement message to neighbour nodes. An example of the operation of start advertisement phase is shown in Figure 13 [61] .

Where, if source node A(xa, ya) aware of the location information of sink node S(xs, ys), node A can easily make the direct segment AS (segment is minimum distance from node to sink; here it is Pa, Pn between node A and sink node S). Position of the node B can be calculated by

(3)

Now the origins of two circles and an intersection of two circles that has limited routing resource is discovered. Therefore, node A can advertise message to its neighbour nodes (D, Z and E). The advertisement message includes a value of Pa, the location information of two circle and intersection.

2) Conditional relay phase: Neighbouring nodes of the source node A decide whether to reply or not depend on the calculation.

(4)

(5)

Figure 13. Start advertisement phase [61] .

and: true

If true, nodes will reply to node A. The reply message will contain energy level information and the Pn value of the corresponding. As shown in Figure 13, node Z will reply with residual energy level and Pz of node Z but node D will drop the advertisement because it fails to satisfy the above conditions.

3) Route selection phase: source node forwards packets to the selected nodes. High energy level and short Pn node will get the high priority.

EELIR collects the neighbour information only when node needs route discovery and thus utilizing the on-demand property to make the protocol energy efficient. Source node transmits data to sink in a unicast manner and conserve the energy. EELIR performs better than the flooding based routing and location aided routing (LAR) in terms of energy consumption, and delivery ratio. It does not have a decent average delay.

4.1.5. ALERT

An anonymous location-based efficient routing protocol (ALERT) [62] , it is distinguished by its low cost and anonymity protection for sources, destinations, and routes. ALERT assumes the entire network area is generally a rectangle in which nodes are randomly disseminated. ALERT uses the hierarchical zone partition and randomly chooses a node in the partitioned zone in each step as an intermediate relay node, thus dynamically generating an unpredictable routing path for a message. In hierarchical zone partition step, they horizontally parti- tion the network into two zones. Then each zone is vertically partitioned. Such zone partitioning consecutively splits the smallest zone in an alternating hori- zontal and vertical manner. Figure 14 shows an example of routing in ALERT where D resides the destination zone, the shaded zone in the figure. Specifically, in the ALERT routing, each data source or forwarder executes the hierarchical zone partition. It first checks whether the nodes itself and destination are in the same zone. If so, it divides the zone alternatively in the horizontal and vertical directions. The node repeats this process until it is in the same zone as the destination node. It then randomly chooses a position in the forwarder node (RF) which is close to its position. In the last step, the data are broadcasted to the nodes in destination zone. In addition, ALERT has a strategy to hide the data initiator among a number of initiators to strengthen the anonymity protection of the source.

4.1.6. DECA

Energy-efficient geographic forwarding algorithm for wireless ad-hoc and sensor network (DECA) [63] is a location-based routing algorithm which main goal is to prolong the network lifetime. It utilizes localized implementation of Dijkstra’s al- gorithm and energy criticality avoidance to choose next hop for packet forwarding. Protocol assumes that each node have the same maximum transmission range, equipped with omni-directional antenna and is able to dynamically adjust its transmission power to communicate with a node in its communication range. It also assumes that each node can estimate the power required to communicate with its direct neighbour and knows its exact position in the network (using GPS or other methods). Residual energy information can be obtained by the periodic local exchange of hello messages to all the neighbours’ nodes. In DECA, each inter-me- diate node uses Dijkstra-like algorithm to its local topology for selecting its best neighbouring hop to reach the destination. It also considers the energy-use efficiency while choosing the best hop to reach the destination. In order to avoid the overusing of energy starving nodes, energy criticality avoidance is enforced which helps to achieve energy draining balancing among nodes. The selection of the node to forward the packet is shown in Figure 15 [63] .

In Figure 15, source node has a packet to send the destination node. Packet can reach up to the destination by three different paths. First, which, total estimated cost is 14.0. Second, which, total estimated cost is 12.7. And third, which, total estimated cost is 12.5. So, Dijkstra algorithm will choose the path which is having the least cost.

Figure 14. Routing among zones in ALERT [62] .

Figure 15. A node x selects its neighbour node to reach destination [63] .

The main idea to prolong the network lifetime is to minimize the per packet end to end delivery which will certainly minimize the energy loss at nodes for packet delivery. Protocol can work in the multiple sink environments. The protocol can also be used for the wireless ad-hoc networks but the complexity per node is high (order of square).

4.1.7. IHLAR

An improved hybrid location-based ad-hoc routing protocol (IHLAR) [64] is a hybrid location-based protocol which combines geographic routing with topology-based routing protocol for ad-hoc network. In IHLAR, each node maintains a table of neighbours within specified numbers of hops (ρ). When a source node or a forwarding node wants to send or forward a packet to a destination node, then first of all it checks whether the node is in the neighbour table. If the destination node resides within ρ hops from the source node or the intermediate node, thus the node will route the packet using AODV protocol, as shown in Figure 16. On the other hand, if the destination node is not present within ρ hops from the source node or the forwarding node, then the packet will be transmitted with greedy forwarding. IHLAR can outperform average delay and packet delivery rate.

4.1.8. LBRP

The Location-Based Routing Protocol (LBRP) [65] is a routing protocol that uses location to exploit position information of nodes and applies a greedy forward- ing approach to route the packets. The routing protocol builds and improves on [66] , which follows a simple distributed approach. The LBRP uses an adaptive transmission power algorithm based on the location information when forwarding packets. This results in energy saving during data transmission and hence prolong the life of the sensor nodes. Figure 17 shows an example of packet routing using LBRP algorithm from source node S to destination node B.

The greedy forwarding approach used in the LBRP algorithm forwards the current node packets to the neighbour node which is closest to the destination node. If a node has a packet to send, it first triggers the Location Service Module (LSM). The LSM provides the location of the next hop on the path to the destination and the location of the destination node. The LSM is responsible for keeping track of the network nodes’ locations. The LSM uses a beacon-based,

Figure 16. Route Setup in IHLAR [64] .

Figure 17. Example of LBRP routing a packet from node A to node B [65] .

some-for-all technique, where some of the nodes know the location details of all other nodes in the network. A source node forwarding a packet adds the location information of destination node in the packet as the next node on the path which will be forwarding the packet towards the destination node needs to know the destination node’s location to forward the packet correctly. The intermediate nodes will use this information as an estimate of the destination’s position unless an updated position is available.

Once a packet is received by an intermediate node, it triggers the LSM to de- termine the next hop node. The intermediate node also extracts the destination location from the packet and updates it if it is aware of a more recent destination location than the one found in the received packet and routes the packet towards the new location. Otherwise, the packet is forwarded without any changes. The latest information about the destination location is determined using sequence numbers stored with the location information. These sequence numbers are extracted from the beacon messages which are periodically broadcasted by the LSM. A higher sequence number means the destination node’s information is recent. LBRP algorithm allows the intermediate nodes to update the destination location and utilizes the velocity information in the LSM. This results in the reduction of the location beaconing frequency and better resource utilization.

The LBRP claims to consume significantly less energy than other protocols during data transmission by adapting the transmit power of the communicating nodes according to the distance between them. As a result, it also claims to extend the battery life and increase the sensor networks availability. Though, the LBRP is never tested on real-life sensor node or a network. The protocol applicability on real sensor nodes is suspected.

4.1.9. SBZRP & LBZRP

This paper [67] proposes two improved zone routing protocol (ZRP), namely selective bordercast in ZRP (SBZRP) and location based selective bordercast in ZRP (LBZRP) to optimize the proactiveness within the zone. Instead of normal bordercast, the border nodes are selected on the basis of connectivity and net- work density. SBZRP is introduced as the first improvement where zones are created dynamically. It is beneficial to have low proactive property; hence the ta- ble formation inside the zone is restricted to some nodes storing the information of next hop to the respective peripheral.

LBZRP is proposed as the second improvement which is an extension of SBZRP and is influenced by location-aided routing (LAR) protocol. Bordercast in LBZRP is limited to the borders which lie on the quadrant relative to the destination’s previous location. LBZRP not only reduces the proactive nature within the zone but also reduces the control flow outside the zone.

4.2. Network Topologies Using Non-Mobile (Static) Nodes

In WSNs, static sensor nodes pose different sets of challenges. In early days of WSNs evolution, a typical network was composed of static sensor nodes and static sinks and most of the routing protocols were proposed considering this fixed setup. In such scenarios, the major cause of energy consumption is the communication module of sensor nodes. As multi-hop communication is re- quired for data transfer and the communication distance plays a major role in energy consumption. Multiple static sinks are used to reduce the communication distance and data is routed from each sensor node to its closest sink. This results in the reduction of energy consumption on individual nodes as well as on overall network due to reduced communication distance and routing load distribution among the nodes respectively. However, while deploying multiple sinks, one has to decide where to place the sinks inside the monitored region so that the data relaying load can be balanced among the nodes. This problem is well-known as a “facility location problem”. If the location information of the static sinks is known, then the solution of this problem can be used for finding the optimal partitioning of the field. However, the nodes close to a sink will still deplete their energy rather rapidly. Static nodes in the network fields depends on the application they are used. For example, forest monitoring for early fire prevention, wild-life monitoring, volcano monitoring etc., require static node development in the field for periodic data collection.

4.2.1. TBF

Trajectory-based forwarding (TBF) [68] is a routing protocol that requires a sufficiently dense network and the presence of a coordinate system, for example, a GPS, so that the sensors can position themselves and estimate distance to their neighbors. TBF is proposed as a middle-ground between source-based routing (SBR) [50] and greedy forwarding techniques [55] . In TBF, the source encodes trajectory to be traversed and embeds it into each packet. Figure 18 shows an example for using trajectory-based routing (TBR) in an application.

Upon arrival of each packet, intermediate nodes decode the trajectory and employ greedy forwarding techniques such that the packet follows its trajectory as much as possible. Route maintenance in TBF is unaffected by sensor mobility given that a source route is a trajectory that does not include the names of the forwarding sensors. In order to increase the reliability and capacity of the network, it is also possible to implement multipath routing in TBF where an alternate path is just another trajectory. Another interesting application of TBF is in securing the perimeter of the network.

4.2.2. BVGF

Bounded voronoi greedy forwarding (BVGF) [69] is a localized algorithm that makes greedy routing decisions based on one-hop neighbor locations. When node i needs to forward a packet, a neighbor j is eligible as the next hop only if the line segment joining the source and the destination of the packet intersects Vor(j) or coincides with one of the boundaries of Vor(j). BVGF chooses as the next hop the neighbor that has the shortest Euclidean distance to the destination among all eligible neighbors. When there are multiple eligible neighbors that are closest to the destination, the routing node randomly chooses one as the next hop.

Figure 19 illustrates four consecutive nodes (si ~ si+3) on the BVGF routing path from source u to destination v. The communication circle of each node is also shown in the figure. We can see that a node’s next hop in a routing path might not be adjacent with it in the Voronoi diagram (e.g., node si does not share a Voronoi edge with node si+1). When Rc ? Rs, this greedy forwarding scheme allows BVGF to achieve a tighter dilation bound than the DT bound that only considers DT edges and does not vary with the range ratio.

It does not help the sensors deplete their battery power uniformly. Each sensor actually has only one next hop to forward its data to the sink. Therefore, any data dissemination path between a source sensor and the sink will always have the same chain of the next hops, which will severely suffer from battery power depletion. BVGF does not consider energy as a metric.

4.2.3. GERAF

Geographic random forwarding (GeRaF) [70] [71] [72] is a geographic routing protocol which also uses an awake/sleep scheduling scheme and MAC protocol. GeRaF assumes that nodes know their positions as well as the sink position. Position can be known by any device like GPS. Nodes do not need store any

Figure 18. An example for using TBR in an application: The application collects photos of the “west of mountains”, which causes best route to be different than traditional shortest-path routing [68] .

Figure 19. A routing path of BVGF [69] .

information about their neighbours and duty cycle (awake/sleep schedule). Node in the network periodically switch to active state and asleep states according to a given duty cycle. If a node has a packet to send, it becomes active and broadcasts a packet. This broadcast packet contains the node location and the location of the destination. To avoid collision, GeRaF uses CSMA/CA MAC protocol. The area which faces the final destination is called as a forwarding area which is divided into priority regions so that all nodes belonging from a region is closer to the destination than any node in a region with lower priority. So, the relay node is picked from the highest-priority region among those that are not empty. Priority region is shown in Figure 20 [70] .

After the broadcast, nodes in the highest priority region contend for forward- ing. If only one node from the region gets the channel, it simply forwards the packet and the process ends. Otherwise, multiple nodes may transmit simulta- neously which will result collision. In case of collision, a resolution technique is applied in order to select a single forwarder. In some cases, it is also possible that any node cannot forward the packet since all nodes in the region are sleeping. To solve this problem, in the next transmission attempt, the relay node will be chosen among nodes in the second highest-priority region and so on. In GeRaF, the relay selection phase will be repeated until a maximum number of retries is reached. In this way, after a hop-by-hop forwarding, the packet will reach up to the intended destination. It is notable that, in GeRaF, relay selection is done a posteriori, and merely requires position information; hence it does not need topological knowledge or routing tables.

4.2.4. ALS

Anchor location service (ALS) [73] protocol is a grid-based protocol that supports location-based routing between multiple moving sources and destinations. ALS provides sink location information in a scalable and efficient manner. ALS as- sumes that each sensor node in the network contains two predefined parameters: α, size of the grid cell and, base line coordinates. Sensor nodes in the sensor field are randomly deployed and obtain their location using an existing positioning mechanism like GPS. After all the sensor nodes are deployed in the field, the following three processes take place:

1) ALS global grid construction process: all the sensor nodes in the field participate in the global grid setup process and with the help of base line coordinates, the coordinates of grid points are determined as follows:

(6)

(7)

where,.

Figure 20. Priority region in GeRaF: increasing priority from A4 to A1 [70] .

Figure 21. The grid node selection process [73] .

The nearest node to the grid point is called grid node and the grid node that take the role of location server for a specific sink called as anchor. The grid node selection process is depicted in Figure 21 [73] .

2) Anchor selection process: multiple destination nodes are possible to be present in the sensor network field. Each destination node selects a neigh- bour node as its sink agent. The sink agent has the responsibility of distributing location information of the destination node using an anchor system. A set of grid nodes constitute the anchor system in which each grid node is called as anchors. This system act as location server.

3) Query and data dissemination process: when an event occurs in the sensor network field, a sensor node will sense the target and will become a source node that will transmit data to a destination node (sink). The source node first registers itself to the nearest grid node which becomes the source agent. The source agent will then transmit four query packets to find the location of sink agent. The anchor system then reports the sink agent information to source node. After receiving the sink agent information, the source node will start sending data packets to the sink agent using a location-based routing protocol.

ALS allows sources to find the location of sinks in a scalable and efficient manner. Multiple sources use the same global grid to find the sink’s location which reduces the communication and storage overhead. This is very important where the communication overhead is of main concern and sensors nodes have limited resources. ALS is used with the GPSR [55] and compared with the grid-based two-tier data dissemination protocol (TTDD) [74] [75] [76] where location time, the communication and state overhead of the protocol is taken as the main performance metrics. These metrics are presented varying the number of sinks and sources, the network size, and the speed of mobile sinks node.

Both ALS and TTDD assumed that sensor nodes are stationary and aware of their location and avoid global flooding to disseminate data and location information. However, the main difference is that TTDD is source-oriented which establishes one grid per source and utilizes the dissemination nodes to distribute both location and data while ALS uses grid nodes to distribute data.

4.2.5. TTDD

As we already summarized, ALS protocol used the advantages of the two-tier data dissemination (TTDD) [75] [76] protocol. Sensor nodes in the field are stationary and the sinks are mobile only. TTDD can work for multiple mobile sink and multiple stationary source nodes. It is assumed that each node knows its lo- cation by using location aware system like GPS or other. Stationary source node in the field proactively builds a grid structure to disseminate data to the mobile sinks. It is using simple greedy geographical forwarding to construct and main- tain the grid structure which causes low overhead. Because of the grid structure for each data source, mobile sinks queries are confined within their local cells only. Because the queries are confined within the local cells, the energy consumption and network overload from global flooding by multiple sinks is avoided.

TTDD assumes that the sensor nodes are aware of their missions, means for a specific type of a stimulus to watch. It also assumes that overhead of mission dissemination is negligible compared to that of sensing data delivery.

When an event occurs in the network, the source node initiate for the grid structure. The source node starts as a crossing point of the grid and sends a data announcement message to each of its four adjacent crossing points using simple greedy geographical forwarding. Once the message reaches on a sensor node that is closest to the crossing point specified in the message, it stops. Now each in- termediate node stores the source information and further forwards the message to its adjacent crossing points except the one from which the message comes. When the message reaches at the border of the network this process will stop. The nodes that store the source information are chosen as dissemination points.

After this process, a grid for the specified source is built and now a sink can flood its queries within a local cell to receive data. The nearest dissemination node on the grid will receive the query which then propagates the query through other dissemination nodes toward the source. The requested data will flow down in the reverse direction to the sink.

In some cases, it is found that the length of a forwarding path in TTDD is longer than the length of the shortest path. TTDD does not work for the mobile nodes in the WSN. Comparison is done between TTDD and directed diffusion [5] [77] and results shows that TTDD is performing better in terms of network lifetimes and delay in data delivery. However, the overhead of maintaining and recalculating the grid in TTDD is high.

4.2.6. EEGR

Energy-efficient geographic routing (EEGR) [78] protocol is a simple, scalable as well as energy efficient. EEGR claims to use both geographic information and transceiver power characteristics to make forwarding decision. It is loop-free and derives the theoretical bounds on number of hops for sensor-to-sink packet delivery. EEGR assumes that radio transceivers in all the nodes are heterogene- ous in terms of transmission range R. It also assumes that every node in the field knows their location as well as the geographic coordinates of the sink through some low cost device like GPS. In EEGR, energy consumed by a node acting as a relay that receives one bit data and then transmits it over distance x is:

(8)

where a1 = a11 + a12 and k (k ≥ 2), k is the propagation loss exponent which is highly depends on the surrounding environment.

In EEGR, packets are transmitted to the neighbour which is closest to the en- ergy optimal relay position instead of forwarding it to the neighbour closest to the sink. By the use of small control messages, the optimal relay node is computed and all nodes are not required to maintain neighbour information. Forwarding process for EEGR is illustrated in Figure 22 [78] .

Where p is the source node and the best relay for it is the neighbour closer to its optimal relay position fp. All nodes neighbour to p need not to participate as relay of p. The relay search region for node p is denoted by Rp, is defined as the circle area cantered at fp with radius rs(p), where rs(p) ≤ |pfp| in Figure 22. Only node Rp will join the relay selection procedure started by the node p. The optimal rs(p) can be estimated according to the node distribution density.

For node p where the distance between p and the sink s is d, if

and d ≤ R, p can directly send its packets to the sink since

transmitting the packets directly is more energy efficient than relaying by other nodes. To deal with the communication overhead, EEGR supports two techniques:

1) The number of reply messages can be controlled by adjusting the size of relay search region because the optimal relay region cover only one neighbour.

2) To further reduce the number of control messages, back-off replaying can be used when there is more than one node in the relay search region.

EEGR is compared with the MFR [79] , GRS [54] , PLRA [80] and GPER [81] . EEGR is 60% more energy efficient than the MFR and GRS. EEGR is performing better than the MFR, GRS and PLRA in terms of transmission range as well.

4.2.7. M-GERAF

M-GERAF (multisink-GERAF) [82] is a data dissemination protocol for multi- sink ad-hoc and WSN. The protocol uses a geographic random forwarding routing approach in order to achieve a reliable data delivery by using an aggres- sive power off strategy without any knowledge of neighbour node position. M-GERAF assumes that sensor nodes are stationary and densely deployed in the

Figure 22. Forwarding process of EEGR [78] .

network field. It uses an awake/sleep scheduling scheme where nodes randomly turn on and off. The protocol also assumes that each node in the network field have some knowledge about its own location and the position of the sink nodes. Sensor nodes can get the position information by the localization device like GPS. When a node has a packet to send, it becomes active and broadcast a packet. This broadcast packet contains the node location and the location of the destination. All the nodes in the coverage area who can listen to the source node receive the packet and schedule the data forwarding based on back-off time. The subset of residual destinations can be given by:

(9)

where, is the position of the actual source node s and Ds = {Ps1, Ps2, ∙∙∙, PsNs} is the data destination set of the source node s.

When a node receives a packet, it will wait for a back-off time, which is computed by its own position, current source node and sink node position values. Following equation is used to compute the back-off time:

(10)

To avoid the collisions, a random period is added to the calculated back-off time. After first retransmission, all the awoken nodes in the first forwarder coverage area remove the first forwarder packet destinations from their own destination set. It is not necessary that all the nodes that forward the received data to the same destination are in the same coverage area. The protocol claims to reduce the amount of transmission by shrinking the αmax, where αmax is the apex angle of the largest conical area. Figure 23 is shown to illustrated αmax, receiver i and destination Sj [82] .

If hence segment i Sj and segment Sj s are quite parallel and

(11)

where is the apex angle of the shrink-est cone in the Sj direction of that contains Pi, as we can see in Figure 23. So, next node residual destination set can be calculated by:

(12)

where, αmax is the maximum allowed cone apex angle.

For the simulation purpose, the whole network field is divided into the hexagonal regions called grids. It is assumed that at least one node is awake in each grid and the awaken node will cover all the adjacent grids. Nodes in the grids nodes switch between sleep and wake state. This random geographic routing approach does not require message loss recovery mechanism because if a packet is not forwarded within a period the transmission will be repeated.

The protocol claims to resolve the problem of reaching a set of destinations

Figure 23. The maximum allowed apex angle, αmax, and the apex of the shrink-est cone in the Sj direction that contain i, αi, j, are depicted [82] .

with only the knowledge of the own and the sink positions but the other optimum problem solution requires complete knowledge of the network and will be computationally unfeasible. The protocol claims to have a fixed overhead that is not related to the sensor amount. Moreover, right parameter tuning allows not correlating the amount of transmission and the sensor density.

M-GERAF ANALYSIS (Multisink―GERAF ANALYSIS) [83] is the extension of the M-GERAF with some modification to reduce the probability of not reaching some destinations and to reduce the delay in data delivery. Back-off time is modified to reduce the average data transmission amount required to reach all the sink nodes.

A new retransmission approach is introduced to enlarge αmax, try a retransmission and not wait for network topology variation. So the probability of reaching the entire sensor node does not immediately fall down if. A slight transmission amount increment is seen due to the αmax sporadic enlargements. In M-GeRaf, back-off calculation only focuses on sink direction and does not take into account the magnitude of the advancement toward destinations. The new evaluation overcomes this limitation and the results show a great performance improvement in terms of transmission amount as well as the energy consumption. An additive Gaussian position error is introduced for correct position estimation error and to then we increase the error process power. Results show that the system performance decreases if the position estimation error could be greater than the average coverage area radius, i.e., nodes could lie over their own believed coverage area.

4.2.8. GF-ViP and GF-MVP

Greedy forwarding with virtual position (GF-ViP) [84] is a geographic routing algorithm based on greedy forwarding strategy. Protocol assumes that each node knows its own position in the network using some localization technique. Pro- tocol introduces the concept of virtual position. Protocol assumes virtual posi- tion of the node as the middle position of all neighbours of node. Instead of se- lecting the geographically near node, GF-ViP uses the virtual position for select- ing the next hop. Greedy forwarding with multi-level virtual position (GF-MVP) is also proposed to utilize the higher level virtual position information. An example for geographic position of node and 1st level virtual position of nodes is shown in Figure 24 [84] .

Virtual position information is stored on the nodes as well as their geographic direct neighbour. Suppose a node A(xa, ya) has node B(xb, yb) , node C(xc, yc) , and node D(xd, yd) as its neighbours then the virtual position of the node A is :

(13)

The higher level virtual position can be calculated in same manner like:

(14)

Using these equations, each node will get its own virtual position and the vir- tual position of its direct neighbour. If node A(xa, ya) wants to send a packet whose destination address is (xd, yd), it will check its own virtual position and the virtual position of all its neighbours. Node A can forward packet to node B (xb, yb) only if it satisfies:

(15)

and,

(16)

GF-ViP deals with hole problem in the network better than the simple greedy forwarding. In a scenario of routing holes, GF-ViP packet success rate is high and the overhead is also low. GF-MVP further increases the packet success rate by utilizing the different level of virtual position. But the overhead will increase with the higher levels of virtual position is used.

4.2.9. GWRR

Loss-aware geographic routing for unreliable WSN (GWRR) [85] is a geographic

Figure 24. Example shows the node and 1st-level virtual position of node in the network [84] .

routing algorithm which mainly focuses on minimizing the number of lost packets in harsh and hostile environment. Protocol assumes that each node is equipped with some localization device. High loss rate region is shown in Figure 25 [85] .

Boundary nodes in Figure 26 are responsible for maintaining topological changes in the loss region. So they have to know each other location. But the other node only knows their neighbours node location. Protocol assigns higher weights to higher harsh regions where each packet is sent hop by hop with a definite probability. The weight of the region is calculated by:

(17)

where, p is the average message loss probability in the faulty region. Weighted region is modelled as a convex polygon. If a boundary node receives a packet

Figure 25. Network field containing the high loss region: Black nodes are lossy nodes, blue nodes are healthy nodes and red nodes are boundary nodes [85] .

Figure 26. Visibility chain of a given node y consists of the nodes which are located between the two tangents and the destination.

whose destination is exterior of the weighted region, then it will decide whether to route the packet through the loss region. The part of the hull which can for- ward packets to the destination in a direct path out of the weighted region are known as the visibility chain for the destination and two boundary node as the top tangent and down tangent. The visibility chain for a node y is shown in Figure 26.

When the route is completely located through the weighted region, forward- ing node assumes only the nodes on the visibility chain. Other possible shortest paths are also possible which consist of routes through the weighted region combined with paths via the perimeter of the area called as mixed type. Protocol applies the contour tracking algorithm [86] to detect the faulty region and boundary nodes. Graham scan algorithm [87] and divide and conquer algorithm [88] is applies for the convex hull. “Monotone Chain” algorithm [89] is used for the convex hull construction. In the protocol, When a forwarding node finds the shortest path through the weighted region, each node forward packets to the closer neighbour to the predefined shortest path hop by hop in a greedy manner.

Results show that it can perform better than DSR and GPSR algorithm in terms of message counts. High loss environment is treated as a weighted region and minimal most paths are found toward the destination through the weighted region. Protocol is developed for the lossy WSN. Results shows only the number of transmitted message in routing with different length but the traffic in the nodes and overhead and energy terms is not discussed.

4.2.10. EEG-Routing

Energy efficient geographic routing (EEG-Routing) [90] is a geographic routing protocol taking sensor position error in to account. It is incredible to attach a GPS device to all nodes since the number of nodes in the network is considerably large. In addition, the localization techniques also cannot provide accurate position for all sensors. So, protocols assume that before the deployment of sensors in the network, sensor positions and position error bounds are known.

Protocol assumes that sensors are static and having the same maximum transmission range r. It also assumes that there is only one sink and is known by all the sensors in the network.

Position error bounds are potentially large (possible up to 100% of transmis- sion range). In accurately position known case, two sensors can communicate if the Euclidean distance between them is less than or equal to their maximum transmission range. But in case of inaccuracy of positions, it is difficult to tell whether two sensors can directly communicate but the communication probability (p) can be calculated. While computing the communication probability there can be three possible cases.

Case 1: two sensors (suppose node A and B) are located with exact positions (= 0, = 0). Then, communication probability can be calculated as:

(18)

where, and is the position error bound for the sensor node A and B.

Case 2: only one sensor is located with an estimated position and the other node is exactly located (,).

(19)

where, S is the area defined by the intersection of the disks centred respectively in A and B, and is the position error bound of node A.

Case 3: Two sensors are located with estimated positions (,). It is shown in Figure 27 and having following possibilities.

1) S1 area contains possible positions for sensor A. when, A and B cannot communicate.

2) S3 area contains possible positions for sensor A. when A and B can communicate.

3) In the S2 area, it is not possible to guarantee if sensors A and B are able to communicate. The probability of communication in S2 has to be estimated.

, (20)

Because, p1 = 0 and p3 = 1.

Where p1, p2 and p3 are communication probabilities where sensor A is located in S1, S2 and S3 respectively.

Ratio between energy consumption and realized progress for RAB (when sensor A sends a message to B) belonging to [0, 1].

(21)

where, j is the energy consumption function, as a function of transmission range d. dopt is optimal transmission range. progAB is progress when A sends a message to sensor B. and it is given that J(dAB) = J(dBA), but as progAB = progBA, so RAB = RBA for arcs (A, B) and (B, A).

Each sensor in the network maintains a table having the cost of the arc to

Figure 27. Sensor B sends a message to sensor A, and > 0 [90] .

reach its neighbour. Cost of the arc (A, B) can be calculated as:

(22)

where and higher value of is good for better energy consumption. But a value near 1 is avoided. When a sensor wants to send a message, it uses sensor position knowledge and sends the message to the neighbour having the least in its cost table. Each message contains the source position, cost of the backup path (second least value in the cost table), a message ID and the event information. When a node receives a message it updates its cost table. Then it selects its neighbour (having least cost) to forward the message.

Message ID of the packet is stored for some time by each node to avoid the loop in the network. A failure node can easily be detected by the HELLO message. EEG-Routing is not compared with the other geographic routing protocol because it is based on the hypothesis, like the knowledge of the node positions with position error bound. However the algorithm result is compared with an energy optimal algorithm. In high density network, delivery rate is very close to 100% which is independent of. But in low density network, low value of is preferred for giving the more importance to progress. Protocol is good for high density network because the energy consumption decreases when the density increases.

Algorithm assumes that position of sensor nodes with position error bound is known before the deployment which is not possible in some cases when large numbers of nodes are deployed in the network. Energy level of the node is not considered in the algorithm which can be an improvement for the algorithm.

4.2.11. SPAN

SPAN [91] is a distributed, randomized algorithm where nodes make local deci- sions on whether to sleep, or join a forwarding backbone as a coordinator. SPAN is motivated by the fact that the wireless network interface of a device is often the single largest consumer of power. Hence, it would be better to turn the radio off during idle time. Each node bases its decision on an estimate of how many of its neighbors will benefit from it being awake and the amount of energy available to it. The main idea of SPAN is to adaptively elect the coordinators from all nodes in the network. SPAN coordinators stay awake continuously and perform multi-hop packet routing within the ad-hoc network while other nodes remain in power-saving mode and periodically check if they should wake up and be- come a coordinator. SPAN is a routing protocol primarily proposed for MANETs, but can be applied to WSNs as its goal is to reduce energy consump- tion of the nodes. Figure 28 shows an example of routing path in SPAN.

4.2.12. Energy Effective Geographical Routing Considering Wireless Link Condition in WSN

Energy effective geographical routing considering wireless link condition in WSN [92] is a geographic routing protocol which considers the wireless link conditions in the network. Protocol assumes that each node have the position information of its direct neighbours. Protocol also assumes that, if the destination node is outside the transmission range of the source node S, the source node S sends the packet to neighbour closest at the distance dop. dop is the distance up to which reliable data transmission is possible. If p is the probability of successfully receiving a packet at a distance d then,

(23)

where, PL(d) is the path loss in dB at distance d, Pn is the noise floor in dBm and f is the frame size of the packet. The transmission strategy adopted in the protocol is showed in Figure 29 [92] .

A node can transmit packet in its connected region with distance r, without an

Figure 28. An example of routing path in SPAN [91] .

Figure 29. Transmission strategy [92] .

error and it can be with or without error in the transitional region. Reliable data transmission is possible within the distance r and no retransmission is needed. When the next node is selected above distance r, the number of hop decreases but the retransmission increases. Relation can be given by:

(24)

where R is the distance from source node to sink node, PW is the power consumption of sending and receiving one packet. Above equation means that if a node is selected at the distance d larger than r as the next hope, energy gain because of reducing the hop count must be greater than energy loss which is caused by the retransmission. The above equation can be rewritten as:

(25)

where distance dop is calculated by using probability p and minimizing the above equation.

Protocol is considering the distance dop which reduces the packet errors and number of retransmissions. Protocol saves the battery power of the node and prolongs the network lifetime. Protocol is analysed numerically. Void nodes are not considered in the protocol.

4.2.13. Low-Latency Geographic Routing for Asynchronous Energy-Harvesting WSNs

Low-latency geographic routing for asynchronous energy-harvesting WSNs [93] uses both geographic and duty-cycle information about the neighbour of the node, to route data efficiently and quickly up to the sink. Energy harvesting is a new technology of getting energy from environmental sources like, solar energy, temperature variations, kinetic energy and vibration. As the energy harvested from the environment can be different from node to node because of the node position and surroundings so each node follows a duty cycle in the protocol. In the geographical routing protocols nodes routes the data packets based on information about its neighbours and the sink. Knowledge range (KR) is the topological extent of this information. A larger KR can give more nearly optimal path, but acquiring and maintaining this topological information require more energy. Protocol uses D-APOLLO algorithm which periodically updates both the KR and duty cycle (DC) of the nodes while considering the information about the local energy budget for the next period. Using this information (KR and DC) in the protocol reduces the end to end delay to the sink.

Protocol avoids the void problem in the network and performs very well in terms of delivery of data and end-to-end delay. The algorithm is focused on maximizing and efficient utilization of the harvested energy of the nodes.

4.2.14. LARP

Location-based adaptive routing protocol (LARP) [94] for underwater acoustic sensor networks is a novel adaptive routing protocol based on the location of the nodes. LARP can select forward route adaptively according to the level of data packets and the dynamic characteristics of underwater environment. The proto- col can classify the data packets into different types according to requirements of application, and select the next hop node depending on the packet level and the characteristics of underwater acoustic channel. LARP selects different route for each packet according to its emergency as shown in Figure 30.

It defines the packets in three different levels: emergent level, intermediate level and ordinary level. Packets with emergent level should be delivered with highest priority and shortest delay to reach to its destination. Therefore, it can reduce the delay of network transmission, save the network energy consumption and improve the quality of the network communication effectively.

4.2.15. LMR

Location-based multicast routing (LMR) [95] is the interference aware energy efficient location-based multicast routing protocol for wireless sensor networks. LMR can outperform the packet delivery ratio and energy by adjusting the energy cost for each link adaptively considering the interference effect and use it

Figure 30. A routing path of LARP from source to destination [94] .

for multicast decision in order to minimize the interference impact. In LMR, a sender node predicts the energy consumption by considering the interference effect. The sender node then delivers a multicast message to the neighbour with the lowest value of energy to each subset of destinations as shown in Figure 31. LMR technique can increase the lifetime and the channel capacity of sensor network by reducing the number of duplicated data transmissions and control messages.

4.2.16. ECMSE

The energy conditioned mean square error algorithm (ECMSE) [96] is the ex- tension work of a similar energy-optimal forwarding choice in the case of the error-robust (CMSER) algorithm [97] and adopts the theoretical energy model [98] . ECMSE is designed for WSN applications in need of efficient, location error-coping geographic routing. In ECMSE, the sensor nodes use low transmission power and the number of required retransmissions are limited with reception acknowledgment. The ECMSE aims for high delivery ratio than similar geographic routing techniques, without compromising on energy efficiency. It ensures quality of services in WSNs while being resilient to the inherent localiza- tion errors of positioning algorithms. The algorithm makes use of statistical as- sumptions of Gaussianly distributed location error and Ricianly distributed dis- tances between sensor nodes. It also makes use of the information about the en- ergy cost of the forwarding decision. The ECMSE provides better results in real- istic simulations as compared to other error-coping geographic routing algo- rithms due to the uses of a location-error resilient and distance-based power metric.

The ECMSE algorithm provides significantly better results than CMSER in terms of both PDR and overall energy consumption. The ECMSE is best suited for large scale scenarios and its performance is conditioned by sensor network density. The algorithm is not designed considering the realistic aspect of com- munication degradation due to channel fading. Furthermore, the CMSER and ECMSE are based on the simplifying assumptions of the location errors and

Figure 31. Selecting the best energy path and forwarding packets in LMR; s: source, d1 ~ d4: destination, v, w: neighbour nodes [95] .

these assumptions are believed to contribute to a less-realistic routing behaviour.

4.2.17. MGEAR

In this paper [99] , the authors proposed an energy efficient geographical routing protocol to minimize the energy consumption of sensor network by using gateway node. The network is separated into four logical regions; in which two regions use direct communication and the rest two regions use clustering hierarchy. Cluster heads are selected in each region independently from other regions based on the probability and residual energy of nodes. The authors claim that the proposed work is a modified version of GEAR [60] .

5. Conclusion

In this paper, we have presented an extensive overview of location-based routing protocols for WSNs which have been presented in the literature. First, we presented a short introduction of WSN, sensor node and their applications followed by short discussion of MAC protocols and some basic ad-hoc network protocols. Then we presented a detailed overview and issues involved with location-based protocols in WSN as well as the advantages and disadvantages of each routing technique. We also presented the design trade-offs between some of the routing paradigms in various matrices such as mobility, energy awareness, QoS, scalability and so on. A table comparing with the different location-based routing protocols is given at the end of this paper.

6. Open Research Issues

Since energy efficiency plays one of the key challenges in resource-constrained WSNs, the routing protocols designed for WSNs should be as energy efficient as possible to prolong the lifetime of individual sensors, and hence it can extend the network lifetime. The most energy consumption action of the sensors takes place from its radio communication especially dominated by data transmission and reception. Therefore, routing protocols designed for WSNs should be aware of energy efficiency in order to extend the lifetime of the sensor network while not compromising on data delivery.

Although many of these routing techniques look promising, there are still many challenges that need to be solved in the sensor networks. We highlighted those challenges and pinpointed future research directions in this regard. Cur- rently, only a few location-based protocols consider mobile WSNs. Further re- search is needed to develop energy efficient location-based routing protocols which will consider whether multiple sources as well as sinks in the network are mobile. For example, several mobile sources and sinks are promising for use in the battle field.

In geographic routing, each node requires its node position information which can be got by the GPS or some localization techniques. It is impractical to equip every node with a GPS system because of the large number of sensor nodes in the network and their cost.

Another desirable interest for future research should be location-based rout- ing for three-dimensional (3D) sensor networks. Although most of research works on WSNs, particularly on routing, consider two-dimensional (2D) net- works, there are some situations where the 2D assumption is not reasonable and the use of a 3D design becomes a necessity. In fact, 3D network reveals more precise location information for real-world applications. Although some efforts have been devoted to the design of routing and data dissemination protocols for 3D sensing applications, more powerful and efficient protocols are required to meet the design requirements of sensor networks.

Cite this paper

Kumar, A., Shwe, H.Y., Wong, K.J. and Chong, P.H.J. (2017) Location-Based Routing Protocols for Wireless Sensor Networks: A Survey. Wireless Sensor Network, 9, 25-72. http://dx.doi.org/10.4236/wsn.2017.91003

References

  1. 1. Savvides, A., Han, C.C. and Strivastava, M.B. (2001) Dynamic Fine-Grained Localization in Ad-Hoc Networks of Sensors. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking (MOBICOM’01), Rome, 16-21 July 2001, 166-179.
    https://doi.org/10.1145/381677.381693

  2. 2. Savvides, A., Park, H. and Srivastava, M.B. (2003) The n-Hop Multilateration Primitive for Node Localization Problems. Mobile Networks and Applications, 8, 443-451.
    https://doi.org/10.1023/A:1024544032357

  3. 3. Savvides, A. and Srivastava, M.B. (2004) Location Discovery. In: Basagni, S., Conti, M., Giordano, S. and Stojmenovic, I., Eds., Mobile Ad Hoc Networking, John Wiley & Sons, Inc., Hoboken.
    https://doi.org/10.1002/0471656895.ch8

  4. 4. Niculescu, D. (2004) Positioning in Ad Hoc Sensor Networks. IEEE Network, 18, 24-29.
    https://doi.org/10.1109/MNET.2004.1316758

  5. 5. Intanagonwiwat, C., Govindan, R. and Estrin, D. (2000) Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks. Proceedings of the 6th Annual International Conference on Mobile Computing and Networking, Boston, 6-11 August 2000, 56-67.
    https://doi.org/10.1145/345910.345920

  6. 6. Srinivasan, K., Dutta, P., Tavakoli, A. and Levis, P. (2006) Understanding the Causes of Packet Delivery Success and Failure in Dense Wireless Sensor Networks. Proceedings of the 4th International Conference on Embedded Networked Sensor Systems (SenSys’06), Boulder, 31 October-3 November 2006, 419-420.
    https://doi.org/10.1145/1182807.1182885

  7. 7. Woo, A., Tong, T. and Culler, D. (2003) Taming the Underlying Challenges of Reliable Multihop Routing in Sensor Networks. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys’03), Los Angeles, 5-7 November 2003, 14-27.
    https://doi.org/10.1145/958491.958494

  8. 8. Zhao, J. and Govindan, R. (2003) Understanding Packet Delivery Performance in Dense Wireless Sensor. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems (SenSys’03), Los Angeles, 5-7 November 2003, 1-13.
    https://doi.org/10.1145/958491.958493

  9. 9. Seada, K., Zuniga, M., Helmy, A. and Krishnamachari, B. (2004) Energy-Efficient Forwarding Strategies for Geographic Routing in Lossy Wireless Sensor Networks. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, 3-5 November 2004, 108-121.
    https://doi.org/10.1145/1031495.1031509

  10. 10. Yick, J., Mukherjee, B. and Ghosal, D. (2008) Wireless Sensor Network Survey. Computer Networks, 52, 2292-2330.
    https://doi.org/10.1016/j.comnet.2008.04.002

  11. 11. Akkaya, K. and Younis, M. (2005) A Survey on Routing Protocols for Wireless Sensor Networks. Ad Hoc Networks, 3, 325-349.
    https://doi.org/10.1016/j.adhoc.2003.09.010

  12. 12. Akyildiz, I.F., Su, W., Sankarasubramaniam, Y. and Cayirci, E. (2002) Wireless Sensor Networks: A Survey. Computer Networks, 38, 393-422.
    https://doi.org/10.1016/S1389-1286(01)00302-4

  13. 13. Nasipuri, A., Cox, R., Conrad, J., Van der Zel, L., Rodriguez, B. and McKosky, R. (2010) Design Considerations for A Large-scale Wireless Sensor Network for Substation Monitoring. IEEE 35th Conference on Local Computer Networks (LCN’10), Denver, 10-14 October 2010, 866-873.

  14. 14. Hur, S., Kim, J., Choi, J. and Park, Y. (2008) An Efficient Addressing Scheme and Its Routing Algorithm for a Large-Scale Wireless Sensor Network. EURASIP Journal on Wireless Communications and Networking, 2008, Article ID: 765803.
    https://doi.org/10.1155/2008/765803

  15. 15. Vieira, M.A.M., Coelho, C.N., da Silva, D.C. and da Mata, J.M. (2003) Survey on Wireless Sensor Network Devices. Proceedings of IEEE Conference on Emerging Technologies and Factory Automation (ETFA’03), 1, 537-544.
    https://doi.org/10.1109/etfa.2003.1247753

  16. 16. Zhu, Z.H. and Yang, S.-H. (2006) A Possible Hardware Architecture of Wireless Sensor Nodes. Proceeding of IEEE Conference on Systems, Man, and Cybernetics, Taipei, 8-11 October 2006, 3377-3381.
    https://doi.org/10.1109/icsmc.2006.384640

  17. 17. http://siliconrobot.com/macro_motes/macromotes.html

  18. 18. Hill, J. and Cullar, D. (2002) A Wireless Embedded Sensor Architecture for System-Level Optimization. Technical Report, University of California at Berkeley.

  19. 19. Calhoun, B.H., Daly, D.C., Verma, N., Finchelstein, D.F., Wentzloff, D.D., Wang, A., Cho, S.-H. and Chandrakasan, A.P. (2005) Design Considerations for Ultra-Low Energy Wireless Microsensor Nodes. IEEE Transactions on Computers, 54, 727-740.
    https://doi.org/10.1109/TC.2005.98

  20. 20. http://www-mtl.mit.edu/researchgroups/icsystems/uamps/

  21. 21. Hill, J.L and Culler, D.E. (2002) Mica: A Wireless Platform for Deeply Embedded Networks. Proceedings of the 35th Annual International Symposium on Microarchitecture, 22, 12-24.
    https://doi.org/10.1109/mm.2002.1134340

  22. 22. http://www.isi.edu/scadds/pc104testbed/guideline.html

  23. 23. Rhee, I., Warrier, A., Aia, M., Min, J. and Sichitiu, M.L. (2008) Z-MAC: A Hybrid MAC for Wireless Sensor Networks. IEEE/ACM Transactions on Networking, 16, 511-524.
    https://doi.org/10.1109/TNET.2007.900704

  24. 24. van Dam, T. and Langendoen, K. (2003) An Adaptive Energy-Efficient MAC Protocol for Wireless Sensor Networks. Proceedings of the 1st International Conference on Embedded Networked Sensor Systems, Los Angeles, 5-7 November 2003, 171-180.
    https://doi.org/10.1145/958491.958512

  25. 25. Du, S., Saha, A.K. and Johnson, D.B. (2007) RMAC: A Routing-Enhanced Duty-Cycle MAC Protocol for Wireless Sensor Networks. Proceeding of the 26th IEEE International Conference on Computer Communications (INFOCOM’07), Anchorage, 6-12 May 2007, 1478-1486.
    https://doi.org/10.1109/infcom.2007.174

  26. 26. Anastasi, G., Conti, M., Di Francesco, M. and Passarella, A. (2009) Energy Conservation in Wireless Sensor Networks: A Survey. Ad Hoc Networks, 7, 537-568.
    https://doi.org/10.1016/j.adhoc.2008.06.003

  27. 27. Joseph, P., Jason, H. and David, C. (2004) Versatile Low Power Media Access for Wireless Sensor Networks. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, 3-5 November 2004, 95-107.

  28. 28. Ye, W., Heidemann, J. and Estrin, D. (2002) An Energy-Efficient MAC Protocol for Wireless Sensor Networks. Proceedings of the IEEE 21st Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’02), 3, 1567-1576.
    https://doi.org/10.1109/infcom.2002.1019408

  29. 29. Peng, W.-C., Ko, Y.-Z. and Lee, W.-C. (2006) On Mining Moving Patterns for Object Tracking Sensor Networks. Proceeding of the 7th International Conference on Mobile Data Management (MDM’06), Nara, 9-13 May 2006, 41.
    https://doi.org/10.1109/MDM.2006.114

  30. 30. Zhang, W. and Cao, G. (2004) DCTC: Dynamic Convoy Tree-Based Collaboration for Target Tracking in Sensor Networks. IEEE Transactions on Wireless Communications, 3, 1689-1701.
    https://doi.org/10.1109/TWC.2004.833443

  31. 31. Cerpa, A., Elson, J., Estrin, D., Girod, L., Hamilton, M. and Zhao, J. (2001) Habitat Monitoring: Application Driver for Wireless Communications Technology. Proceeding of ACM Workshop on Data Communication in Latin America and the Caribbean, 31, 20-41.
    https://doi.org/10.1145/844193.844196

  32. 32. Chen, C.-C. and Liao, C.-H. (2011) Model-Based Object Tracking in Wireless Sensor Networks. Wireless Networks, 17, 549-565.
    https://doi.org/10.1007/s11276-010-0296-5

  33. 33. Chen, T.-S., Liao, W.-H., Huang, M.-D. and Tsai, H.-W. (2005) Dynamic Object Tracking in Wireless Sensor Networks. Proceeding of the 13th IEEE International Conference on Networks (ICON’05), Kuala Lumpur, Malaysia, 16-18 November 2005, 475-480.

  34. 34. Milenkovic, A., Otto, C. and Jovanov, E. (2006) Wireless Sensor Networks for Personal Health Monitoring: Issues and An Implementation. Computer Communications, 29, 2521-2533.
    https://doi.org/10.1016/j.comcom.2006.02.011

  35. 35. Alemdar, H. and Ersoy, C. (2010) Wireless Sensor Networks for Healthcare: A Survey. Computer Networks, 54, 2688-2710.
    https://doi.org/10.1016/j.comnet.2010.05.003

  36. 36. Kulkarni, P. and Ozturk, Y. (2011) mPHASiS: Mobile Patient Healthcare and Sensor Information System. Journal of Network and Computer Applications, 34, 402-417.
    https://doi.org/10.1016/j.jnca.2010.03.030

  37. 37. Ding, D., Cooper, R.A., Pasquina, P.F. and Fici-Pasquina, L. (2011) Sensor Technology for Smart Homes. Maturitas, 69, 131-136.
    https://doi.org/10.1016/j.maturitas.2011.03.016

  38. 38. Boers, I.M., Chodos, D., Gburzynski, P., Guirguis, L., Huang, J., Lederer, R., Liu, L., Sadowski, C. and Stroulia, E. (2011) The Smart Condo Project: Services for Independent Living. E-Health, Assistive Technologies and Applications for Assisted Living: Challenges and Solutions. IGI Global, 289-314.
    https://doi.org/10.4018/978-1-60960-469-1.ch013

  39. 39. Han, D.-M. and Lim, J.-H. (2010) Smart Home Energy Management System Using IEEE 802.15.4 and Zigbee. Proceeding of IEEE Transactions on Consumer Electronics, 56, 1403-1410.
    https://doi.org/10.1109/TCE.2010.5606276

  40. 40. Xu, Y. and Lee, W.-C. (2007) Compressing Moving Object Trajectory in Wireless Sensor Networks. International Journal of Distributed Sensor Networks, 3, 151-174.
    https://doi.org/10.1080/15501320701204756

  41. 41. Chen, W., Chen, L., Chen, Z. and Tu, S. (2005) A Realtime Dynamic Traffic Control System Based on Wireless Sensor Network. Proceeding of the International Conference on Parallel Processing (ICPP’05), 14-17 June 2005, 258-264.

  42. 42. He, T., Krishnamurthy, S., Luo, L., Yan, T., Gu, L., Stoleru, R., Zhou, G., Cao, Q., Vicaire, P., Stankovic, J.A., Abdelzaher, T.F., Hui, J. and Krogh, B. (2006) VigilNet: An Integrated Sensor Network System for Energy-Efficient Surveillance. ACM Transactions on Sensor Networks, 2, 1-38.
    https://doi.org/10.1145/1138127.1138128

  43. 43. Selavo, L., Wood, A., Cao, Q., Sookoor, T., Liu, H., Srinivasan, A., Wu, Y., Kang, W., Stankovic, J., Young, D. and Porter, J. (2007) LUSTER: Wireless Sensor Network for Environmental Research. Proceedings of the 5th International Conference on Embedded Networked Sensor Systems, Sydney, 6-9 November 2007, 103-116.
    https://doi.org/10.1145/1322263.1322274

  44. 44. Xu, N., Rangwala, S., Chintalapudi, K.K., Ganesan, D., Broad, A., Govindan, R. and Estrin, D. (2004) A Wireless Sensor Network for Structural Monitoring. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, 3-5 November 2004, 13-24.
    https://doi.org/10.1145/1031495.1031498

  45. 45. Zhang, P., Sadler, C.M., Lyon, S.A. and Martonosi, M. (2004) Hardware Design Experiences in ZebraNet. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems, Baltimore, 3-5 November 2004, 227-238.
    https://doi.org/10.1145/1031495.1031522

  46. 46. http://wildcense.sourceforge.net/

  47. 47. Simon, G., Balogh, G., Pap, G., Maróti, M., Kusy, B., Sallai, J., Lédeczi, á., Nádas, A. and Frampton, K. (2004) Sensor Network-Based Countersniper System. Proceedings of the 2nd International Conference on Embedded Networked Sensor Systems (SenSys’04), Baltimore, 3-5 November 2004, 1-12.
    https://doi.org/10.1145/1031495.1031497

  48. 48. Huang, J.-H., Amjad, S. and Mishra, S. (2005) CenWits: A Sensor-Based Loosely Coupled Search and Rescue System Using Witnesses. Proceedings of the 3rd International Conference on Embedded Networked Sensor Systems, San Diego, 2-4 November 2005, 180-191.
    https://doi.org/10.1145/1098918.1098938

  49. 49. Werner-Allen, G., Lorincz, K., Ruiz, M., Marcillo, O., Johnson, J., Lees, J. and Welsh, M. (2006) Deploying a Wireless Sensor Network on an Active Volcano. IEEE Internet Computing, 10, 18-25.
    https://doi.org/10.1109/MIC.2006.26

  50. 50. Johnson, D.B. and Maltz, D.A. (1996) Dynamic Source Routing in Ad-Hoc Wireless Networks. In: Imielinski, T. and Korth, H., Eds., Mobile Computing, Kluwer Academic Publishers, 153-181.
    https://doi.org/10.1007/978-0-585-29603-6_5

  51. 51. Perkins, C.E. and Bhagwat, P. (1994) Highly Dynamic Destination-Sequenced Distance-Vector routing (DSDV) for Mobile Computers. ACM SIGCOMM Computer Communication Review, 24, 234-244.
    https://doi.org/10.1145/190809.190336

  52. 52. Park, V.D. and Corson, M.S. (1997) Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks. Proceedings of the 16th Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM’97), Kobe, 9 -11 April 1997, 1405-1413.

  53. 53. Perkins, C.E. and Royer, E.M. (1999) Ad-Hoc On-Demand Distance Vector Routing. Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications (WMCSA’99), New Orleans, 25-26 February 1999, 90-100.
    https://doi.org/10.1109/MCSA.1999.749281

  54. 54. Finn, G.G. (1987) Routing and Addressing Problems in Large Metropolitan Scale Internetworks. USC/ISI Technical Report ISI/RR, March 1987, 87-180.

  55. 55. Karp, B. and Kung, H.T. (2000) GPSR: Greedy Perimeter Stateless Routing for Wireless Networks. Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom), Boston, 6-11 August 2000, 243-254.
    https://doi.org/10.1145/345910.345953

  56. 56. Ko, Y.-B. and Vaidya, N.H. (1998) Location-Aided Routing (LAR) in Mobile Ad-Hoc Networks. Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, Dallas, Texas, United States, 25-30 October 1998, 66-75.
    https://doi.org/10.1145/288235.288252

  57. 57. Rodoplu, V. and Meng, T.H. (1999) Minimum Energy Mobile Wireless Networks. IEEE Journal on Selected Areas in Communications, 17, 1333-1344.
    https://doi.org/10.1109/49.779917

  58. 58. Li, L. and Halpern, J.Y. (2001) Minimum-Energy Mobile Wireless Networks Revisited. Proceeding of IEEE International Conference on Communications (ICC’01), Helsinki, 11-14 June 2001, 278-283.

  59. 59. Xu, Y., Heidemann, J. and Estrin, D. (2001) Geography-Informed Energy Conservation for Ad Hoc Routing. Proceedings of the 7th Annual International Conference on Mobile Computing and Networking, Rome, Italy, 16-21 July 2001, 70-84.
    https://doi.org/10.1145/381677.381685

  60. 60. Yu, Y., Estrin, D. and Govindan, R. (2001) Geographical and Energy Aware Routing: A Recursive Data Dissemination Protocol for Wireless Sensor Networks. UCLA Computer Science Department Technical Report.

  61. 61. Kim, K., Yun, J., Yun, J., Lee, B. and Han, K. (2009) A Location Based Routing Protocol in Mobile Sensor Networks. Proceedings of the 11th International Conference on Advanced Communication Technology (ICACT’09), Phoenix Park, 15-18 February 2009, 1342-1345.

  62. 62. Shen, H. and Zhao, L. (2013) ALERT: An Anonymous Location-Based Efficient Routing Protocol in MANETs. IEEE Transactions on Mobile Computing, 12, 1079-1093.
    https://doi.org/10.1109/TMC.2012.65

  63. 63. Yu, Q., Zhang, B., Liu, C. and Mouftah, H.T. (2008) Energy-Efficient Geographical Forwarding Algorithm for Wireless Ad Hoc and Sensor Networks. Proceedings of the IEEE Wireless Communications and Networking Conference (WCNC’08), Las Vegas, 31 March-3 April 2008, 2468-2473.
    https://doi.org/10.1109/wcnc.2008.434

  64. 64. Luo, D. and Zhou, J. (2011) An Improved Hybrid Location-Based Routing Protocol for Ad Hoc Networks. Proceedings of the 7th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM), Wuhan, 23-25 September, 1-4.
    https://doi.org/10.1109/wicom.2011.6040306

  65. 65. Sammut, E. and Debono, C.J. (2015) A Location-Based Routing Algorithm for Wireless Sensor Networks. Proceedings of IEEE International Conference on Computer as a Tool (EUROCON’15), Salamanca, 8-11 September 2015, 1-5.
    https://doi.org/10.1109/eurocon.2015.7313687

  66. 66. Sun, M.-T., Sakai, K., Hamilton, B.R., Ku, W.-S. and Ma, X. (2011) G-STAR: Geometric STAteless Routing for 3-D Wireless Sensor Networks. Ad Hoc Networks, 9, 341-354.
    https://doi.org/10.1016/j.adhoc.2010.07.013

  67. 67. Malwe, S.R., Rohilla, S. and Biswas, G.P. (2016) Location and Selective-Bordercast Based Enhancement of Zone Routing Protocol. 3rd International Conference on Recent Advances in Information Technology (RAIT), Dhanbad, 3-5 March 2016, 83-88.
    https://doi.org/10.1109/rait.2016.7507880

  68. 68. Yuksel, M., Pradhan, R. and Kalyanaraman, S. (2002) TBF: Trajectory-Based Forwarding Mechanisms for Ad-HOC Networks. Wireless Networks, 8, 481-494.

  69. 69. Xing, G., Lu, C., Pless, R. and Huang, Q. (2004) On Greedy Geographic Routing Algorithms in Sensing-Covered Networks. Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing, Tokyo, 24-26 May 2004, 31-42.
    https://doi.org/10.1145/989459.989465

  70. 70. Zorzi, M. and Rao, R. (2003) Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Multihop Performance. IEEE Transaction on Mobile Computing, 2, 337-348.
    https://doi.org/10.1109/TMC.2003.1255648

  71. 71. Zorzi, M. and Rao, R. (2003) Geographic Random Forwarding (GeRaF) for Ad Hoc and Sensor Networks: Energy and Latency Performance. IEEE Transactions on Mobile Computing, 2, 349-365.
    https://doi.org/10.1109/TMC.2003.1255650

  72. 72. Casari, P., Marcucci, A., Nati, M., Petrioli, C. and Zorzi, M. (2005) A Detailed Simulation Study of Geographic Random Forwarding (GERAF) in Wireless Sensor Networks. Proceedings of the IEEE Military Communications Conference (MIL-COM’05), Atlantic City, 17-20 October 2005, 59-68.

  73. 73. Zhang, R., Zhao, H. and Labrador, M.A. (2006) The Anchor Location Service (ALS) Protocol for Large-Scale Wireless Sensor Networks. Proceedings of the 1st International Conference on Integrated Internet Ad-Hoc and Sensor Networks, Nice, 30-31 May, 2006, Article No. 18.
    https://doi.org/10.1145/1142680.1142704

  74. 74. Fan, Y. (2002) TTDD Simulation. Unpublished Work, 26 February 2002.

  75. 75. Ye, F., Luo, H., Cheng, J., Lu, S. and Zhang, L. (2002) A Two-Tier Data Dissemination Model for Large-Scale Wireless Sensor Networks. Proceedings of the 8th Annual International Conference on Mobile Computing and Networking (MOBI-COM’02), Atlanta, 23-28 September, 2002, 148-159.

  76. 76. Luo, H., Ye, F., Cheng, J., Lu, S. and Zhang, L. (2005) TTDD: Two-Tier Data Dissemination in Large-Scale Wireless Sensor Networks. Wireless Networks, 11, 161-175.
    https://doi.org/10.1007/s11276-004-4753-x

  77. 77. Intanagonwiwat, C., Govindan, R., Estrin, D., Heidemann, J. and Silva, F. (2003) Directed Diffusion for Wireless Sensor Networking. IEEE/ACM Transaction on Networking, 11, 2-16.
    https://doi.org/10.1109/TNET.2002.808417

  78. 78. Zhang, H. and Shen, H. (2007) EEGR: Energy-Efficient Geographic Routing in Wireless Sensor Networks. Proceedings of the 36th International Conference on Parallel Processing (ICPP’07), Xi’an, 10-14 September 2007, 67.
    https://doi.org/10.1109/icpp.2007.37

  79. 79. Takagi, H. and Kleinrock, L. (1984) Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals. IEEE Transactions on Communications, 32, 246-257.
    https://doi.org/10.1109/TCOM.1984.1096061

  80. 80. Stojmenovic, I. and Lin, X. (2001) Power-Aware Localized Routing in Wireless Networks. IEEE Transactions on Parallel and Distributed Systems, 12, 1122-1133.
    https://doi.org/10.1109/71.969123

  81. 81. Wu, S. and Candan, K.S. (2004) GPER: Geographic Power Efficient Routing in Sensor Networks. Proceedings of the 12th International Conference on Network Protocols (ICNP’04), Berlin, 8 October 2004, 161-172.

  82. 82. Odorizzi, A. and Mazzini, G. (2007) M-GERAF: A Reliable Random Forwarding Geographic Routing Protocol in Multisink Ad-Hoc and Sensor Networks. International Symposium on Intelligent Signal Processing and Communication Systems (ISPACS’07), Xiamen, 28 November-1 December 2007, 416-419.
    https://doi.org/10.1109/ispacs.2007.4445912

  83. 83. Odorizzi, A. and Mazzini, G. (2008) M-GeRaf Analysis: Performance Improvement of a Multisink Ad-Hoc and Sensor Network Geographical Random Routing Protocol. Proceedings of the 16th IEEE International Conference on Software, Telecommunications and Computer Networks (SoftCOM’08), Split, 25-27 September 2008, 193-197.
    https://doi.org/10.1109/softcom.2008.4669478

  84. 84. You, J., Lieckfeldt, D. and Timmermann, D. (2009) Tendency-Based Geographic Routing for Sensor Networks. Proceedings of the 6th IEEE Consumer Communications and Networking Conference (CCNC’09), Las Vegas, 10-13 January 2009, 1-2.
    https://doi.org/10.1109/ccnc.2009.4784706

  85. 85. Ghadimi, E., Khonsari, A., Talebi, M.S. and Yazdani, N. (2009) Loss-Aware Geographic Routing for Unreliable Wireless Sensor Networks. Proceedings of the 6th IEEE Consumer Communications and Networking Conference (CCNC’09), Las Vegas, 10-13 January 2009, 1-5.

  86. 86. Zhu, X., Sarkar, R., Gao, J. and Mitchell, J.S.B. (2008) Light-Weight Contour Tracking in Wireless Sensor Networks. Proceedings of the IEEE 27th Conference on Computer Communications (INFOCOM’08), Phoenix, 13-18 April 2008, 1175-1183.
    https://doi.org/10.1109/infocom.2008.173

  87. 87. Graham, R.L. (1972) An Efficient Algorithm for Determining the Convex Hull of a Finite Point Set. Information Processing Letters, 1, 132-133.
    https://doi.org/10.1016/0020-0190(72)90045-2

  88. 88. Preparata, F.P. and Hong, S.J. (1977) Convex Hulls of Finite Sets of Points in Two and Three Dimensions. Communications of the ACM, 20, 87-93.
    https://doi.org/10.1145/359423.359430

  89. 89. Andrew, A.M. (1979) Another Efficient Algorithm for Convex Hulls in Two Dimensions. Information Processing Letters, 9, 216-219.
    https://doi.org/10.1016/0020-0190(79)90072-3

  90. 90. Champ, J. and Saad, C. (2008) An Energy-Efficient Geographic Routing with Location Errors in Wireless Sensor Networks. Proceedings of the International Symposium on Parallel Architectures, Algorithms, and Networks (I-SPAN’08), Sydney, 7-9 May 2008, 105-110.

  91. 91. Chen, B., Jamieson, K., Balakrishnan, H. and Morris, R. (2002) Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks. Wireless Networks, 8, 481-494.
    https://doi.org/10.1023/A:1016542229220

  92. 92. Sim, I. and Lee, J. (2008) Energy Effective Geographical Routing Considering Wireless Link Condition in WSN. Proceedings of the International Conference on Multimedia and Ubiquitous Engineering (MUE’08), Busan, 24-26 April 2008, 582-585.

  93. 93. Noh, D., Yoon, I. and Shin, H. (2008) Low-Latency Geographic Routing for Asynchronous Energy-Harvesting WSNs. Journal of Networks, 3, 78-85.

  94. 94. Li, J.L., Du, X., Xing, J. and Yang, Q. (2012) Location-Based Adaptive Routing Protocol for Underwater Acoustic Sensor Networks. Proceedings of the International Conference on Automatic Control and Artificial Intelligence (ACAI’12), Xiamen, 3-5 March, 1315-1319.

  95. 95. Cha, J., Jeon, J., Kim, J. and Kwon, Y. (2010) Location-Based Multicast Routing Algorithms for Wireless Sensor Networks in Presence of Interferences. Proceedings of the IEEE International Conference on Communication Systems (ICCS), Singapore, 17-19 November 2010, 41-45.

  96. 96. Popescu, A.M., Salman, N. and Kemp, A.H. (2014) Energy Efficient Geographic Routing Robust Against Location Errors. IEEE Sensors Journal, 14, 1944-1951.
    https://doi.org/10.1109/JSEN.2014.2305832

  97. 97. Popescu, A.M., Salman, N. and Kemp, A.H. (2013) Geographic Routing Resilient to Location Errors. IEEE Wireless Communications Letters, 2, 203-206.
    https://doi.org/10.1109/WCL.2013.011713.120849

  98. 98. Peng, B. and Kemp, A.H. (2011) Energy-Efficient Geographic Routing in the Presence of Localization Errors. Computer Networks, 55, 856-872.
    https://doi.org/10.1016/j.comnet.2010.10.020

  99. 99. Singh, P.K., Prajapati, A.K., Singh, A. and Singh, R.K. (2016) Modified Geographical Energy-Aware Routing Protocol in Wireless Sensor Networks. International Conference on Emerging Trends in Electrical Electronics & Sustainable Energy Systems (ICETEESES), Sultanpur, 11-12 March 2016, 208-212.
    https://doi.org/10.1109/ICETEESES.2016.7581386