Keywords
|
| wireless sensor network; geographic routing; cross layer design; load balancing |
INTRODUCTION
|
| Wireless Sensor Network (WSN) is intended for monitoring an environment. The main task of a wireless sensor node is to sense and collect data from a certain domain, process them and transmit it to the sink where the application lies. However, ensuring the direct communication between a sensor and the sink may force nodes to emit their messages with such a high power that their resources could be quickly depleted. Therefore, the collaboration of nodes to ensure that distant nodes communicate with the sink is a requirement. Sensor networks are networks of small embedded low-power devices that can operate unattended to monitor and measure different phenomena in the environment. Sensor networks are suited for applications such as habitat monitoring, infrastructure protection, security, and tracking [1] [2]. |
| Basically, each sensor node comprises sensing, processing, transmission, mobilize, position finding system, and power units (some of these components are optional like the mobilizer). |
| The Figure 1 shows the communication architecture of a WSN. Geographic protocols, that take advantage of the location information of nodes, are very valuable for sensor networks. In the following sections describes literature review with an extensive overview of geographic routing with its various protocols. |
LITERATURE REVIEW
|
| Ding, Sivalingam, Kashyapa, and Chuan [3] considered the problem of finding a route from a sensor to the single sink in a wireless sensor network. Following a reactive route discovery strategy, the sink floods the network and sets the routes. The difference is that each sensor does not memorize the whole route, or a single pointer to predecessor sensor on the route, but instead it memorizes its hop count distance to the sink. When a packet is sent toward the sink, any neighbor at one less hop distance can forward it, instead of reporting back to the first node that sent task assignment packet to it. The simplest form of geographic routing is Greedy routing which was first described by Finn in 1987 [3]. In the greedy routing algorithm, each node in the route forwards packets to the neighbor which is the closest to the destination among its neighbors. Only the neighbors that are closer to the destination than the current node are considered. The first geographic routing was described by Takagi and Kleinrock [4]. The notion of progress was introduced to define the most forward within radius (MFR) greedy routing algorithm. Kranakis, Singh and Urrutia proposed another strategy of geographic routing utilizes direction information of next hop candidates with respect to line toward the destination called compass routing (also referred to as the DIR method) in [4]. |
| Stojmenovic and Lin [5] proved that Greedy, GEDIR and MFR routing are loop-free while DIR routing is not. Greedy routing selects the neighbor which is closer to the destination than the current node. There is no backtracking and thus it is loop-free. All routing protocols based on the cost to progress ratio can be improved by applying the iterative improvement method which was described by Huang, Dai and Wu (for QoS metric costs). |
| Stojmenovic and Lin [5] proposed flooding based methods, called f-greedy and f-MFR , which apply greedy routing and MFR at intermediate nodes and run a recovery mechanism at concave nodes. |
| A localized DFS (Depth First Search)-based routing algorithm was proposed by Stojmenovic, Russell and Vukojevic [6]. Different from f-greedy, DFS is single path routing. Each node remembers if it has already been visited by the DFS traversal, and the node from where the message was received for the first time. Kranakis, Singh and Urrutia [6] described the first localized memory less routing algorithm for planar geometric graphs, which guarantees delivery whenever source and destination are connected. Morin, Stojmenovic and Urrutia [5] proposed a combination of the face routing algorithm with the distance-based greedy routing. The algorithm that is referred to as GFG (Greedy-Face-Greedy) applies greedy algorithm until the packet reaches a node such that all its neighbors are further from the destination than the node itself. The face routing is applied until the packet reaches another node that is strictly closer to the destination. The greedy algorithm is then resumed. The algorithm can switch between greedy and face mode several times, but guarantees progress and delivery because face routing is always successful, and loop-free. The GFG algorithm was further improved by Datta, Stojmenovic and Wu [6] to reduce its average hop count. Each forwarding node uses the local 2-hop information available to calculate as many hops as possible and forwards the message to the last known hop directly instead of forwarding it to the next hop. |
| GFG algorithm with added IEEE 802.11 medium access layer was later implemented as the greedy perimeter stateless routing (GPSR) protocol by Karp and Kung [7]. Heissenbuttel and Braun proposed the beaconless routing (BLR) algorithm in [11]. The BLR was further integrated with the IEEE 802.11 MAC layer in the contention-based forwarding (CBF) by Füßler et al [FWKMH03] and implicit geographic forwarding (IGF) by Blum et al [BHSS03]. Zorzi [8] proposed to avoid duplicate forwarding in a BLR scheme by employing the request-to-send/clear-to-send (RTS/CTS) MAC scheme from IEEE 802.11. The current node sends an RTS signal instead of the message and waits for a CTS signal. If several responses are received, the node selects the one that appears to be the best for forwarding and then sends the message to that neighbor directly. The distance-based greedy forwarding has been first introduced by Finn in [8]. In this case the closer node that minimizes the Euclidean distance from the destination is selected as next-hop relay. Seada et al. are the first to provide a systematic and more formal study of the effects of localization errors on geographic routing for WSNs [9]. They focus on dead end recovery through planar graph traversal. Helmy et al. [10] model and analyze the impact of location inconsistencies on the two main phases of geographic routing (i.e., greedy forwarding and perimeter traversal). The authors also propose an improvements of the GPSR [11] protocol for taking into account the effect of location errors induced by mobility. The authors observe that the main reason for packet drop induced by localization errors is false local maximum, i.e., nodes that believe to be dead ends because the estimated coordinates are affected by error. |
ROUTING IN WIRELESS SENSOR NETWORK
|
| In general, routing in WSNs can be divided into flat-based routing, hierarchical-based routing, and location-based routing depending on the network structure shown in Figure 2. In flat-based routing, all nodes are typically assigned equal roles or functionality. In hierarchical-based routing, however, nodes will play different roles in the network. In location-based routing, sensor nodes positions are exploited to route data in the network. A routing protocol is considered adaptive if certain system parameters can be controlled in order to adapt to the current network conditions and available energy levels. Furthermore, these protocols can be classified into multipath-based, query-based, negotiation-based, QoS-based, or coherent-based routing techniques depending on the protocol operation. In addition routing protocols can be classified into three categories, namely, proactive, reactive, and hybrid protocols depending on how the source finds a route to the destination. In proactive protocols, all routes are computed before they are really needed, while in reactive protocols, routes are computed on demand. Hybrid protocols use a combination of these two ideas [12].When sensor nodes are static, it is preferable to have table driven routing protocols rather than using reactive protocols. A significant amount of energy is used in route discovery and setup of reactive protocols. Another class of routing protocols is called the cooperative routing protocols, in which, nodes send data to a central node where data can be aggregated and used to further processing, hence reducing route cost in terms of energy use. Many other protocols rely on timing and position information. |
GEOGRAPHIC ROUTING
|
| Geographic routing (also known as position-based routing or geometric routing) is a technique to deliver a message to a node in a network over multiple hops by means of position information. Routing decisions are not based on network addresses and routing tables; instead, messages are routed towards a destination location. With knowledge of the neighbor’s location, each node can select the next hop neighbor that is closer to the destination, and thus advance towards the destination in each step. The fact that neither routing tables nor route discovery activities are necessary makes geographic routing attractive for dynamic networks such as wireless ad hoc and sensor networks. In such networks, acquiring and maintaining routing information is costly as it involves additional message transmissions that require energy and bandwidth and frequent updates in mobile and dynamic scenarios. |
| Geographic routing algorithms use position information for making packet forwarding decisions. Unlike topological routing algorithms, they do not need to exchange and maintain routing information and work nearly stateless. This makes geographic routing attractive for wireless adhoc and sensor networks. |
A. Greedy forwarding
|
| Most geographic routing algorithms use a greedy strategy that tries to approach the destination in each step [13], e.g. by selecting the neighbor closest to the destination as a next hop depicted in Figure 3. However, greedy forwarding fails in local minimum situations, i.e. when reaching a node that is closer to the destination than all its neighbors. A widely adopted approach to solve this situation is planar graph routing. |
| A simple greedy forwarding by minimizing the distance to the destination location in each step cannot guarantee message delivery. Nodes usually have a limited transmission range and thus there are situations where no neighbor is closer to the destination than the node currently holding the message. Greedy algorithms cannot resolve such dead-end or local minimum situation. |
B. Planar graph
|
| Planar graph routing, which guides the packet around the local minimum and guarantees delivery, required that a planar sub graph of the network graph can be constructed in Figure 4. Therefore, recovery methods have been developed, the most prominent of which are based on planar graph routing, where the message is guided around the local minimum by traversing the edges of a planar sub graph of the network communication graph[14]. Planar graph routing techniques can provide delivery guarantees under certain assumption. Altogether, greedy forwarding in combination with a recovery can be considered as state-of-the-art technique in geographic routing. |
C. Challenges in geographic routing
|
| The current geographic routing schemes fail to fully address some important design challenges, including |
| i) Routing around connectivity holes, |
| ii) Resilience to localization errors, and |
| iii) Efficient relay selection. |
LOAD-BALANCING IN GEOGRAPHIC ROUTING
|
| Load-balancing is needed to effectively use available sources and keep the nodes energy consumption balanced by equally distributing the load[15]. The problem is to route data packets avoiding congested path so as to balance traffic load over network and lower end-to-end delay. Distributing the load within the network has two advantages. i) First, resource of the network is fully utilized through distributing network load. An efficient load-balancing routing protocol is able to improve packet delivery rate and network throughput. ii) Second, energy consumption is balanced by equally distributed load, so that the network lifetime could be prolonged. A dynamic parameter less load-balancing geo routing protocols was proposed. The node holding the packet for delivery compares costs of sending the packet to all available neighbors that are closer to destination and not fully loaded, against the progress made. The cost is then increasing linearly with the consumed bandwidth. |
A. Adaptive Load-Balancing Algorithm, Rainbow
|
| Packet delivery is guarantee to the sink in any connected topology without suffering from the overhead and the inaccuracies incurred by planar methods, called Adaptive Load-Balancing Algorithm, Rainbow version (ALBA-R for short), which is a simple, distributed scheme that is remarkably resilient to localization errors and independent of whether or not the network topology is modeled by a unit disk graph.[16] [17] In particular, ALBA-R integrates contention-based MAC principles, geographic routing concepts, and an algorithm to avoid the dead end problem, and proves to be very robust and applicable to realistic scenarios. In addition, ALBA-R directly addresses the important issue of load balancing in routing the packets, including explicitly congestion metrics in the relay selection process. The design of ALBA-R follows recent trends in geographic routing protocol cross-layer design [18] [19] where the availability and exchange of information among different (possibly non-adjacent) protocol layers, as well as the direct integration of the functionalities of multiple layers, allow a node to make more effective routing decisions based on a wider view of the network, leading to greatly improved overall performance. |
CONCLUSION
|
| Wireless sensor network with its routing classification, mainly focused on geographic routing. Geographic routing concentrates on location of each nodes, neighbors and destination of wireless sensor network. Geographic routing includes cross-layer design, avoid dead end problem, resilience to localization error. The greedy forwarding and face routing plays a vital role in geographic routing. The load balancing mechanism of geographic routing with its protocol is discussed in detail. The load balancing algorithm has the advantage of network throughput and maximum lifetime. Geographic routing protocols achieve better performance in packet delivery and low energy consumption is discussed in this paper through a survey. |
| |
Figures at a glance
|
 |
 |
 |
 |
| Figure 1 |
Figure 2 |
Figure 3 |
Figure 4 |
|
| |
References
|
- Akyildiz, W. Su, Y. Sankarasubramaniam, and E. Cayirci, "A survey on sensor networks," IEEE Communications Magazine, Volume: 40 Issue: 8, pp.102-114, August 2002.
- P. Bose, P. Morin, I. Stojmenovic, J. Urrutia, “Routing with Guaranteed Delivery in Ad Hoc Wireless Networks,” in Proc. of 3rd ACM Int. Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIAL M99),pp.48-55, 1999.
- S. Datta , I. Stojmenovic, J. Wu, “Internal node and shortcut based routing with guaranteed delivery in wireless networks,” Cluster Computing, vol. 5, no. 2, pp. 169-178, 2002.
- J. Ding, K. M. Sivalingam, R. Kashyapa, and L. J. Chuan. “A multi-layered architecture and protocols for large-scale wireless sensor networks,” Proc. IEEE Vehicular Technology Conference (VCT2003), Orlando, USA, October 2003.
- Ferrara, D., Galluccio, L., Morabito, G., Leonardi, A., And Palazzo, S.Macro: An integrated MAC/routing protocol for geographical forwarding in wireless sensor network. In Proceedings of the 24th IEEE Annual Conference on Computer Communications,INFOCOM 2005
- Fraser Cadger, Member, Kevin Curran, IEEE, Jose Santos and Sandra Moffett “A Survey of Geographical Routing in Wireless Ad- Hoc Networks “, IEEE Communications Surveys and Tutorials, Vol. PP, No. 99, pp: 1-33, 2012.
- H. Füßler, J. Widmer, M. Kasemann, M. Mauve, H. Hartenstein, “Contention-based Forwarding for Mobile Ad-hoc Networks,” Ad Hoc Networks, vol.1, no. 4, pp. 351-369, 2003.M. Heissenbuttel, T. Braun, “BLR: Beacon-less Routing Algorithm for Mobile Ad-hoc Networks,” Computer Communications, vol. 27, no. 11, pp. 1076-1086, 2004.
- B. Karp, H.T. Kung, “GPSR: Greedy Perimeter Stateless Routing for Wireless Networks,” in Proc. of The 6th ACM/IEEE Annual International Conference on Mobile Computing and Networking (MobiCom-00), pp. 243-254, 2000.
- Kim, Y., Lee, J., And Helmy, A. “Modeling and analyzing the impact of location inconsistencies on geographic routing in wireless networks”.SIGMOBILE Mob.Comput.Commun. Rev. 8, 1, 2004.
- E. Kranakis, H. Singh, J. Urrutia, “Compass Routing on Geometric Networks,” in Proc. of the 11th Canadian Conference on Computational Geometry (CCCG’99), pp. 51-54, 1999.
- J. Kuruvila, A. Nayak, I. Stojmenovic, “Progress Based Localized Power and Cost Aware Routing Algorithms for Ad Hoc and Sensor Wireless Networks,” in Proc.of The 3rd International Conference on Ad-Hoc Networks and Wireless (ADHOCNOW2004), LNCS 3158, pp. 294-299, 2004.
- Rama SundariBattula, O. S. Khanna “Geographic Routing Protocols for Wireless Sensor Networks: A Review”,International Journal of Engineering and Innovative Technology (IJEIT) Volume 2, Issue 12, June 2013
- SEADA, K., HELMY, A., AND GOVINDAN, R. “On the effect of localization errors on geographic face routing in sensor networks”.In Proceedings of the 3rd IEEE/ACM International Symposiumon Information Processing in Sensor Networks, IPSN 2004 (Berkeley, CA, Apr. 2004).
- Shakkottai, S., Rappaport, T. S., And Karlsson, P. C. Cross–layer design for wireless networks. IEEE Commun. Mag. 41, October 2003.
- D. Son, A. H., And Krishnamachari, B. “The effect of mobility-induced location errors on geographic routing in mobile ad hoc and sensor networks: analysis and improvement using mobility prediction”. IEEE Trans. Mobile Comput. 3, 3 July 2004.
- Stojmenovic, X. Lin, “Loop-free Hybrid Single-Path / Flooding Routing Algorithms with Guaranteed Delivery for Wireless Networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 10, pp. 1023-1032, 2001.
- H. Takagi, L. Kleinrock, “Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals,” IEEE Transactions on Communications, vol. 32, no. 3, pp. 246-257, 1984.
- M. Zorzi, “A New Contension-based MAC Protocol for Geographic Forwarding in Ad Hoc and Sensor Networks,” in Proc. of The IEEE International Conference on Communications (ICC 2004), vol. 16, pp. 3481-3485, 2004.
|
Menu