Abstract
Sensor networks are large-scale distributed sensing networks comprised of many small sensing devices equipped with memory, processors, and short-range wireless communication radio. Instead of broadcast tbased routing protocols, in this paper we propose a novel energy-efficient routing protocol, which is called Straight Line Routing Algorithm1 (SLR), for wireless sensor networks. To achieve the routing task without broadcasting, the source host constructs the event path and the sink host constructs the query path respectively. That is, the routing path is found as the query path and the event path first intersect. Moreover, the SLR is able to build both the query path and the event path without any help of the geographic information. We evaluate the performance of Straight Line Routing and Rumor Routing protocols through extensive simulations. The simulation results indicate that compared with Rumor Routing, the SLR can save more energy consumption, provide better path quality, and improve the successful ratio of routing as well.
Introduction
In the near future, advances in processor, memory, and radio technology will enable small and cheap nodes capable of wireless communication and significant computation. Networks comprised of such nodes can coordinate to perform distributed sensing of environment phenomena. Therefore, there are a lot of applications for sensor networks. For instance, sensor nets often are installed in monitoring system, such as Structure Health Monitoring (SHM), which could be used to monitor human healthy anytime and anywhere. Another example is to monitor the degree of temperature or the density of dust around a volcano to predict the eruption time.
(DSR) do in ad hoc networks. However, these broadcast-based routing protocols are not appropriate for a sensor network since the broadcast is a costly operation. Frequent broadcasts drain the sensor battery off quickly. In addition, it is difficult to recharge or replace the sensor nodes that run out of energy and
are distributed widely over the geographic area. Another type of routing protocols is the random walk-based protocol. Without triggering every sensor node to generate a routing message, random-walk based protocol limits the propagation of routing message among partial sensor nodes. Gossip and Rumor are two famous random-walk-based routing protocols. Gossip has focused on multicast or broadcast services in the Internet and does not take wireless environment features, such as power constrain and high error rate of the wireless channel, into account. Thus, in this paper we are interested in another routing protocol - Rumor Routing. In Rumor Routing protocol, every node has to maintain its neighbor list. When propagating a routing message, the node appends its neighbor list in that routing message.
Consequently, the message will record every node that has received this message. By examining such visited list, the node can choose a neighbor node that has not received this message, and keep the routing away from growing in the “backward” direction. The advantage of Rumor Routing is simple to implement but with the following drawbacks.
Network Assumption
In this section we first state some basic assumptions about the sensornets in this work. Sensornets comprise the nodes that are spread out, randomly or in some pattern over some well-defined area. Nodes only haves hort-range communication, but also are inside radio range of several other nodes. The communication power of all nodes in sensornets is equal. Energy is a scarce resource for sensor nodes. Using a node’s wireless communication requires energy. We note that target signal amplitude attenuates, as a monotonically decreasing function of the distance from the source, according to an inverse distance squared law or exponentially. When a node receives a packet successfully, it is able to tell which node sending this packet and measure the signal strength. That is, we assume that all nodes are aware of energy model. After receiving a packet, each node has the ability of determining the distance from the source according to the signal strength. Now, we give an introduction about how to figure out a routing path in the sensor network. When a sensor node detects an interesting event, it starts to invoke the routing mechanism for the event path. This routing path for the event is growing straight until it hits the border or the path length is equal to some constant. That is, a fixed-length path is constructed, and all nodes along this path keep the event information. On the other hand, there is a special node that will request events on the sensor network. We refer to this node as the “Sink”. Similarly, when the sink queries an event, it also executes the routing mechanism. A query path will be constructed by the same routing scheme. When the query path intersects the corresponding event path, the routing path is completed. The intersection node is called the anchor node, and the anchor needs to reply an ACK message to the Sink when it has been created.
SLR Overview
The main idea of the SLR protocol is to keep the routing path straight. Like Rumor Routing, SLRconstructs the path in the hop-by-hop type. In each hop, we need to choose a node, which lies on the extended line of the path, as the next hop. Fig. 1 illustrates the original idea. Suppose node b in Fig. 1 is the newest hop, node a is the pre-hop of node b, (Obviously, the direction of the path is from a to b) and the distance between them is R/2 where R is the radio distance. We focus on the intersection of a’s and b’s radio ranges and consider our new coordinate system. We define the first dimension as the distance from node a and the second dimension as the distance from node b. It is clear the node, whose location is (R, R/2), is the most suitable node to be the next hop in the intersection message. Unfortunately, the node in the position (R, R/2) does not always exist. We need to modify our algorithm for adapting to this situation. Before introducing the algorithm, we define some interest regions associated with a node. Outside Band and Inside Band of node n are referred to the circular band regions where the center is node n and the radius are R and R/2, respectively.
The basic concept of Straight Routing Algorithm is illustrated as Fig. 2. We assume node A is the current hop, and node B is the previous hop. Shown as Figure 2, we can observe that the intersected region of Inside Band of node A and Outside Band of node B provides a proper set of nodes for choosing the next hop. We name this intersected region Candidate Region, and the next hop will be chosen from nodes inside it. We designed two steps in our routing protocol. First step, the Candidate Region will be determined. Then, the second step is to choose a node from Candidate Region as the next hop.
Step 1:
For each routing, every node will maintain two variables, FlagIn and FlagOut. Based on our assumptions, after a node receives a route request, this node can calculate the distance from the sender to itself. By the way, the node can recognize itself in which band of the source. If it is in the Inside band, it will enable its FlagIn. On the other hand, if it is in the Outside band, it will enable its Flagout.. A node will start contending to be the next hop only when its two variables, FlagIn and FlagOut, both have been enabled, because it is in the Candidate Region.
Step 2:
Subsequently, every node in Candidate Region will set its own timer, Twait. In this work, we set the formula in the form of Twait =1/distparent +1/distgradnparent. This means it has the best possibility to become the next hop node. When its timer expires, the node will issue a message to notify its neighbors. Besides the node that has become the next hop node, other nodes in Candidate Region will overhear the notifying message. After receiving the message, nodes will stop the contention procedure.
Improvements
Based on the discussion above, we consider the case of low network density. The situations that there is no node in the Candidate Region may often be suffered, and these situations will cause SLR can’t pick up any node as the next hop. Therefore SLR is terminated usually before finishing constructing the path when the node-density is low.
Intuitively, the probability that the situation (empty Candidate Region) happens is inverse-proportional
with the size of the Candidate Region. Unfortunately, in order to choose a better node and to make the path straight, SLR refines the area of the Candidate Region by receiving twice route messages. This feature makes the success probability of SLR degrade considerably on low-density networks. In addition to the terminated probability, another drawback of SLR is the long delay
of its routing procedure. Because of the method of refining Candidate Region, the longest distance of
every hop (from the next node to the present) is the half of transmission radius. That means the routing procedure of SLR needs more time, and the hop count of the path is larger than general protocols such as Rumor.
For the purpose to adapt SLR to low-density sensor nets, the probability of successful path discovery and the path quality (i.e., hop count) can be enhanced. We devise four improvement schemes as the followed:
1. Adjusting the widths of Inside Band and
Outside Band
2. SLR Dual Way
3. SLR Far Jump
4. SLR Short-Cut ACK
Adjusting the widths of Inside Band and Outside Band
Obviously, the size of the Candidate Region is directly related to the width of Inside Band and
Outside Band. Moreover, the width affects the bending-angle of the path at every hop. For example, we observe that to decrease gbOut (Outside Band width) or gbIn (Inside Band width) will decrease the size of the Candidate Region and bending-angle of the path both. Decreasing the bending-angle makes the path straighter but the terminated-probability higher. In the contrast, increasing the size of the Candidate Region makes bending-angle smaller, but the probability of successful path discovery becomes higher. Therefore, now our task is to determine the values of gbOut (Outside Band width) and gbIn (Inside Band width). At first we observe the Fig. 3 and suppose the transmission radius R is 1. The range of gbOut value will be deduced roughly. We obtain
<(1- gbOut)<1
ð 0< gbOut <
In this work, we set the Inside Band a plate (i.e.,gbin=1), and the size Candidate Region just depends on the value of gbOut.
SLR Dual Way
In basic SLR, the initial direction of the path is chosen by source randomly. However, if the initial direction is totally backward the destination, the path is getting worse and worse during path construction, because the SLR always keeps the path straight. Nevertheless, it deserves to be mentioned that the inverse direction is a good choice in this case. Based on this observation, we develop another scheme to improve SLR, which is the so-called SLR_DW. In the beginning (shown in (a)), the source node S broadcasts a routing message within its communication
range. After receiving this message the nodes in the Inside Band of S (ex: A, B, C, D) set their FlagIn 1, while the nodes in the Outside Band (ex: E, F, G, L, H, I, J, K) set their Flagout 1.
Then (illustrated with (b)) a node (e.q., node A) has been chosen as the next hop, so the direction from S to A is the initial direction. After node A rebroadcasts this message, the nodes in the Inside Band of A (e.q. E, F, G) set their FlagIn 1 (demonstrated by (c)). At the same time, the nodes in
the Outside Band of A (node C) set their Flagout 1. That means there is the path whose initial direction is from A to C has been generated. Hereafter, the both paths of different directions will be constructed individually.
SLR Far Jump
The prerequisite to enlarge the area of the Candidate Region is that every node is able to detect whether the Candidate Region is empty or not. For this reason, when a node transfers a routing message, it will set a timer and wait. No notifying message heard before the timer expires indicates that no node in the Candidate Region.
In this subsection we introduce the mechanism to enlarge the Candidate Region, SLR Far Jump. When the timer expires, the node will issue the SLR_FJ message, which the new length of Inside Band radius is recorded in. Therefore it is expectable that more neighbours will set their FlagIn 1 after hearing this SLR_FJ message. However, dislike the basic SLR, the nodes whose pair (FlagIn, FlagOut) is equal to (1,0), instead of (1,1), will contend to be the next hop. The reason can be explained through Fig. 5. For the current node, the gray area of Fig. 5 is suitable to be the new Candidate Region. The pairs (FlagIn, FlagOut) of the nodes in this area are equal to (1,0). Nevertheless, it is emphatic that the principle described above has to be used once again after the SLR Far Jump. This is because the distance of the hop decided by SLR Far Jump is longer than R/2. Consider the next hop choice. If we apply the principle of the basic SLR (That is, (FlagIn, FlagOut) = (1,1)), the Candidate Region decided may not be suitable. Conversely, adopting the rule above ((FlagIn, FlagOut) = (1,0)) once again will determine the Candidate Region just like Fig. 5, which is more reasonable
SLR Short-Cut ACK
In basic SLR, the distance per hop is a half of radio distance at most. That means the routing procedure of SLR needs more time, and the hop count of the path is larger. In this subsection, we take advantage of ACK messages to reduce the hop count of the path that has been constructed. We call this mechanism SLR Short- Cut ACK.
As the network assumptions, when two corresponding paths cross, the anchor (i.e., the intersection node) will reply the ACK message to the Sink node. It is interesting the propagation of the ACK
message will stride across two hops at least. As the case illustrated by Fig. 6, when a node transfers an ACK message, at least two nodes along the path will receive it. In fact, according to the feature of triangles (shown in Fig. 6 (c)) there are three nodes receiving the message. Because the node will retransfer the ACK after receiving it, the response time and path length (hop count) are shorter than the original.
Performance Evaluation
In this section, we evaluate the performance of SLR by simulations. In our simulations, nodes are scattered randomly on a two-dimensional field. A simple radial propagation model was used, where each node could reliably send packets to any node within its communication range RTX. Four combinations of protocols, which are SLR/SLR, SLR/RR, RR/SLR, RR/RR respectively are compared. The notation formed “a/b” indicates the protocols to construct the event path (initialized from sensor nodes) and the query path (initialized from the sink node), respectively. (“RR” means the Rumor Routing). The criteria are energy cost, successful ratio, and hop count of the path averagely per routing.
small topology
In this scenario, we set NTotal=500, BX=500, BY=500, nPathsrc=1, nPathdst=1, nHopdst=10, gbsrc Out=0.3 and gbdst Out=0.6. Fig. 7 shows the success ratio and energy cost of four protocol pairs respectively. We can find that SLR can find more paths. Moreover, SLR/SLR and SLR/RR are much superior to RR/RR when transmission range is 70. This means the improvement of SLR adapts to the sparse networks respectably. When the radio radius is 100, because the successful ratio of SLR/RR is much higher, SLR/RR consumes more batteries than RR/RR. In addition, we compared the average hop count of the path. It is noticed that we only compared the paths which were searched successfully. The results are listed on the table below, and these show the benefit of the SLR Short Cut ACK. We specially observed the performance of one flooding-based protocol, AODV. The path searched by flooding-based routing scheme is viewed as the shortest path. As we expected, the path length of SLR/SLR is the smallest. Conversely, RR/RR makes the longest path for the same reason. By the way, the path of SLR/RR is shorter than RR/SLR’s because the event path is fix-length. When the spiral problem happens, the query message needs to pass more nodes in order to reach the event path.
Scheme
Average hops
SLR/SLR 5.497667
SLR/RR 5.682305
RR/SLR 7.310626
RR/RR 7.616045
Flooding Based 3.3534
large topology
We set parameters as NTotal=2000, BX=1000, BY=1000, nPathsrc=1, nPathdst=1, nPathdst=10, Gbsrc Out=0.3 and gbdst Out=0.6, to create a large-scale network. By comparing the correspond results in Fig. 7 and 8, we can find that the performance of RR degrades very much in large-scale networks, but SLR still maintains the high efficiency. This is because the spiral problem becomes serious in the large-scale network. In small-scale networks, the distance of the sink and the event is not too long. Even there are many meanderings in the query path, but it is very probable the query path crosses the event path. However, these situations happen seldom when the scale of the network is large. Therefore, the successful ratio and energy cost of RR deteriorate in the huge-scope sensor network, because the routing message of RR will pass numbers of nodes, and the unfixed searching direction
makes the two paths intersect more difficultly.
Conclusions
Random-walk-based routing is a new routing protocol category without broadcasting procedures. To reduce the number of meanderings in the path, a novel random-walk routing protocol, SLR, has been proposed in this paper. This protocol aims to choose every hop in the original direction of the path. The simulation shows that the straight path can enhance the successful ratio of routing, and lower the energy cost.
No comments:
Post a Comment
leave your opinion