Abstract: In multimedia wireless sensor networks, multiple packets are generated for the same destination. All these packets go through the same route in a session when using current geographical routing. However, detour is inevitable in geographical routing without the help of global state. A progressive yet effective strategy is proposed to mitigate inefficient detour in geographical routing. In asymptotically optimal geographical routing, detour mode was substituted by greedy mode with the help of a subset of nodes acting as way points. The average performance of the proposed algorithm is compared to Greedy Perimeter Stateless Routing (GPSR) and the benchmark shortest path algorithm. Simulation results show that in average the proposed algorithm can reduce as much as 50% of hops on the routes obtained by GPSR.
INTRODUCTION
With the progress of MEMS (Micro-Electro-Mechanical Systems), the availability of small, inexpensive low-power global positioning system unit has enhanced the use of geographical routing (Imielinski and Navas, 1999). Geographical routing protocols share 2 assumptions. First, every node is assumed to know its own and its direct neighbors’ positions. Second, the header of the packet includes geographical information of the destination. After receiving a packet, every node greedily forwards the packet to its neighbor geographically closest to the destination. This is referred to as the greedy forwarding mode or greedy mode. If a route is discovered by only using greedy forwarding mode, the route is known to be sub-optimal (Kuhn et al., 2002). Greedy forwarding behaves well in practice, but it fails to yield a path to the destination when it encounters a void area, where no node exists. Without a routing table, different protocols have different strategies to find a detour to the destination with various criteria. This is referred to as the detouring mode. In a word, geographical routing is a promising routing method for Wireless Sensor Networks (WSN) due to its simplicity and scalability (Mauve et al., 2001).
Karp’s GPSR protocol is a well-known geographical routing algorithm and suited for highly dynamic environments such as inter-vehicle communication on highways (Karp and Kung, 2000). In GPSR, a detour is found by traversing on the faces of the planar graph, which can result in excessive number of hops. On the other hand, location-aided routing uses flooding in route discovery (Ko and Vaidya, 2000). Detours found by flooding the network are optimal but too expensive and not preferred. To reduce the excessive number of hops caused by detour mode and save energy, anchor-based geographical routing has been proposed. In Blazevic et al. (2005), a list of anchors is written by the source into the packet header. In Huang (2004), a small number of bits in a packet header are used to encode the salient features of a route. However, these methods need to maintain a long list of node locations in the packet header when used for large-scale sensor networks, which may be of high overhead. Furthermore, it is unnecessary and energy-wasting to add these additional bits for every packet. In essence, these methods sacrifice information rate for hop reduction. In Ma et al. (2006), pruning based routing schemes are proposed to improve the efficiency of routing, which finds routing shortcuts by exploiting the channel listening capability of wireless nodes. However, it is indispensable that each node listens to the channel for a long period of time even if there is no shortcut. Moreover, its improvement is limited because it was restricted by the radius of communication. This is usually not possible for sparse sensor network.
In essence, the detour mode contains excessive hops when shorter ones are available, which results in higher energy consumption. Traffic on the perimeter of a void area can be high and nodes along the perimeter of the void area can deplete faster (Al-Karaki and Kamal, 2004). As a result, the lifetime of the network is reduced. Therefore, detour mode should be avoided.
In many network applications, such as multimedia communications, the source frequently sends multiple packets to the same destination (Akyildiz et al., 2007; Gurses and Akan, 2005). If the network topology remains static during a connection session, all packets sharing the same destination will go through exactly the same route. In other words, if the first packet goes through a lengthy detour to reach its destination, all the subsequent packets will suffer in a similar manner (Ma et al., 2006).
Inefficient detour mode in multimedia WSN motivates us to investigate algorithms to improve the path found by various detour strategies. In this study, we propose an Asymptotically Optimal Geographical Routing (AOGR). In our approach, the reference of delivered packets to subsequent packets in routing will be exploited. By selecting some nodes as way points, the route will be controlled by the source and the destination plus these way points. It possesses the following desired properties:
| • | Routing gradually converges to the optimal path |
| • | The algorithm can be embedded in existing geographical routing protocols |
| • | The algorithm incurs little storage overhead in a small number of nodes |
The performance of the proposed routing algorithm AOGR is measured by comparing its average hop count with greedy perimeter stateless routing (Karp and Kung, 2000) and the benchmark shortest path. Simulation results show that our algorithm significantly improves the performance of geographical routing by reducing as much as 50% of hops on the routes of GPSR.
ASYMPTOTICALLY OPTIMAL GEOGRAPHICAL ROUTING
Here, we first briefly explain the strategy behind our protocol. We then provide the pseudo code of the asymptotically optimal geographical routing protocol.
The route obtained by GPSR is shown in solid line in Fig. 1. Way points are similar to the node in GPSR when the packet switches from perimeter mode to greedy mode, such as A and B. A and B are neighboring way points. After B delivers a packet, it only sends its geographical information to A by greedy mode. On receiving B’s message, A can immediately tell that there is a shortcut between them. A sets its next way point with B. The dashed line (i.e., SA and AB) in Fig. 1 shows that they are shortcuts. After receiving a subsequent packet with the same destination, A will forwards it to B. Actually, B acts as A’s virtual destination.
| Fig. 1: | Routes of two geographical routing schemes. S: Source
node and D: Destination node, (a) the route obtained by GPSR (solid
line) and (b) the route obtained by AOGR (dashed line) |
A set of way points will be chosen as the packet makes its journey in the network until the destination is reached. Hence, the route is controlled by these way points. Between way points, greedy geographical routing is used for forwarding. By this way, multi-hops optimum will be achieved by one-hop optimum. The route is a concatenation of greedy forwarded route segments. While, a route in current geographical routing protocols is uniquely determined by the positions of the source and destination, a route in AOGR is determined not only by the positions of the source and destination but also by these way points. It is precisely the anchor acted by the way points that provides space for optimization of routes, and the lack of it that makes greedy mode inefficient for some network topologies (Huang , 2004).
Although, the feedback channel is needed, it does not conflict with forward channel. The overhead is mainly a number of nodes that have to save the position of next way point, and there is no flooding and broadcasting of global network state; so the scalability of geographical routing is retained (Ma et al., 2006). In addition, the header of the packet is unchanged, so the proposed protocol can be embedded in current geographical routing, such as GPSR.
The distance between 2 nodes ni and nj is denoted as dist (ni, nj). Let the neighbors of node ni be denoted as nbr(ni). For a packet m, let nd denote the destination of m. The current mode of m is denoted as m.mode, which can be either greedy or detour. The current data of m is denoted as m.data. In my simulations, m.data is used to record the position of the way point. In applications, only the initial or the first packet is used to choose way points.
Using these denotations, the proposed asymptotically optimal geographical routing protocol shown below:
A node ni holding packet m runs the following:
| ni forwards m to the way point greedily |
SIMULATIONS RESULTS
To evaluate the proposed algorithm, 3 sets of simulations are conducted using the ns-2. We consider the following 3 kinds of network topology: O-shape topology, C-shape topology and ∞-shape topology. The total area of void is 30% of the total area of the network. Three examples are shown in Fig. 2. There are 150 nodes covering a 200x200 dm area. The communication radius of each node is fixed at 20 dm.
Average performance improvement: The performance of an algorithm A on a network is defined as:
where, n is the packet sequence number; sA(N, s d, n) is the number of steps obtained by routing algorithm A on network N finding a route from s to d; |sp(N, s, d)| is the hops of the shortest path between the source s and the destination d on network N.
For a given set of simulation, k independent runs are conducted to minimize the possible bias for a particular network topology. Then, the average performance of algorithm A is defined as:
We compare AOGR with GPSR and the benchmark shortest path algorithm. Multiple data packets are sent from the source to the destination. Each packet follows the same route by using the current geographical routing protocol, such as GPSR. The result is shown in Fig. 3. Using the proposed protocol, the route will be optimized step by step. The first packet is delivered along the GPSR route and a set of way points will be chosen, while the subsequent packets can be forwarded guided by these way points.
| Fig. 2: | Three
examples of different network topology. The x-axis is the width of
deployed area and the y-axis is the length of deployed area, (a) GPSR
and AOGR routing for O-shape network topology (GPSR: 36 hops; AOGR:
18 hops), (b) GPSR and AOGR routing for C-shape network topology (GPSR:
44 hops; AOGR: 19 hops) and (c) GPSR and AOGR routing for 8-shape
network topology (GPSR: 39 hops; AOGR: 16 hops). S: Source node and
D: Destination node |
| Fig. 3: | Average performance comparison |
| Fig: 4: | Storage over head of AOGR. The y-axis represents the overhead of two algorithms |
As delivered packets increase, the proposed algorithm converges to the shortest path gradually for 3 kinds of network topology. As shown in Fig. 2a-c, the GPSR route has 36, 44 and 39 hops, respectively, while the AOGR route has only 18, 19 and 16 hops. In this sense, the proposed algorithm reduces as much as 50% of hops on the routes obtained by GPSR.
Storage overhead: Storage overhead only incurs in way points. The location of the source takes the role of the first way point. The location of the final destination takes the role of the last way point. As for the number of way points, it depends on the number and the shape of the void region.
From Fig. 4, we observe that in average, less than 10 nodes of the original route are way points and need to store extra information. Considering the significant performance improvement as shown in Fig. 2 and 3, the extra storage overhead of the proposed algorithm is well justified.
| Fig. 5: | The speed of node and the frequency of updating way points vs. the percentage of changed way points |
Mobility: The change of node’s position will affect its role in the routing. Figure 5 shows the percentage of changed way point under different speeds of the node and different frequencies of updating way points. In this study, changed way point is defined as the node that it was way point and is not now. The percentage of changed way point is defined as the ratio of the number of changed way point and the number of total way points on the original route. The result suggests that the higher the speed of the node, the higher the percentage of changed way point. On the other hand, higher frequency of updating way points means lower percentage of changed way points. Although, way points are necessary to mitigate inefficient routing, the failure of a way point will not increase packet loss rate. This is because pure greedy forwarding mode will be substituted by greedy forwarding mode and detour mode. Therefore, the robustness of geographical routing is retained.
Scalability: Although, geographical routing protocols are completely stateless, the proposed protocol has added a little storage overhead in node but no extra communication and computation overheads are needed. The way point nodes store next way point based on the geographical location of the destination, instead of the position of the source and thus subsequent packets to the same destination could also take advantage of the way point nodes. This will reduce the overall network routing overhead in the presence of multiple-source and single-sink topology networks (Ma et al., 2006). From this perspective, the proposed algorithm is also a scalable one.
CONCLUSION
In many network applications, such as multimedia WSN, multiple packets generated from the same source are delivered to the same destination and all packets will go through exactly the same path by current geographical routing. In this study, we proposed an asymptotic approach for improving the efficiency of detour mode in geographical routing and demonstrated the asymptotic schemes’ effectiveness. With the help of way points acted by a subset of nodes on the route, the proposed algorithm is capable of reducing a large portion of hops commonly created by the detour mode. It has been shown that present algorithm has strength in routing performance efficiency by reducing as much as 50% hops on the route of GPSR.
ACKNOWLEDGMENTS
This research is supported by National Natural Science Foundation of China with Grant No. 60673061 and The National Key Technology R and D Program of China with Grant No. 2007BAK23B03.