21-02-2012, 02:54 PM
Straight Line Routing for Wireless Sensor Networks
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.
1. 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.
Since sensor nodes are scattered over the entire sensing area, communication between sensor nodes is usually in a hop-by-hop manner. This is similar as the traditional distributed routing protocols such as Destination Sequenced Distance Vector [2](DSDV), Ad Hoc On-Demand Distance Vector [1] (AODV), and Dynamic Source Routing [3]
(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 [4] and Rumor [5] 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.
Spiral Problem
Rumor routing is able to avoid searching the path in the backward direction, but unable to figure out a
better direction for the routing path. In other words, such routing scheme might generate a lot of meanderings along the routing path. The worst case could be formed as a spiral. Furthermore, the winding path consists of more nodes than the straight path does, i.e., compared with the straight path, the response time of the winding path is longer and the total consumed energy of the winding path is larger as well.
Waste Energy in recording visited nodes in packet’s payload
In Rumor Routing, paths are constructed in a hopby- hop manner. In order to avoid choosing backward nodes, the current node first examines the visited list to select an unvisited node as the next hop, appends all its neighbors’ IDs in packet payload and then transmits the routing packet to that chosen node. Hence, the size of the routing packet is expected to become larger and larger and the node has to consume more and more energy to transmit this routing packet. To avoid the spiral problems, the intuition is to reduce the number of meanderings in the routing path. Therefore, in this work we propose a novel randomwalk- based routing protocol --- Straight Line Routing (SLR), which aims to make the routing path grow as straight as possible.
2. 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.
3. 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.
4. 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.
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.
1. 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.
Since sensor nodes are scattered over the entire sensing area, communication between sensor nodes is usually in a hop-by-hop manner. This is similar as the traditional distributed routing protocols such as Destination Sequenced Distance Vector [2](DSDV), Ad Hoc On-Demand Distance Vector [1] (AODV), and Dynamic Source Routing [3]
(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 [4] and Rumor [5] 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.
Spiral Problem
Rumor routing is able to avoid searching the path in the backward direction, but unable to figure out a
better direction for the routing path. In other words, such routing scheme might generate a lot of meanderings along the routing path. The worst case could be formed as a spiral. Furthermore, the winding path consists of more nodes than the straight path does, i.e., compared with the straight path, the response time of the winding path is longer and the total consumed energy of the winding path is larger as well.
Waste Energy in recording visited nodes in packet’s payload
In Rumor Routing, paths are constructed in a hopby- hop manner. In order to avoid choosing backward nodes, the current node first examines the visited list to select an unvisited node as the next hop, appends all its neighbors’ IDs in packet payload and then transmits the routing packet to that chosen node. Hence, the size of the routing packet is expected to become larger and larger and the node has to consume more and more energy to transmit this routing packet. To avoid the spiral problems, the intuition is to reduce the number of meanderings in the routing path. Therefore, in this work we propose a novel randomwalk- based routing protocol --- Straight Line Routing (SLR), which aims to make the routing path grow as straight as possible.
2. 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.
3. 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.
4. 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.