Abstract: Directed Diffusion (DD) is an energy-efficient data dissemination scheme in order to extending the lifetime of the wireless sensor networks. However, original DD is based on shortest path routing, which will deplete quickly the energy of nodes lying along the often used optimal paths. To avoid this, this paper extends DD based on the idea of energy equivalence. A source routing Directed Diffusion (SR-DD) is proposed in order to avoid local "hotspots" which DD possibly forms. The sink chooses one from several paths based on the residual energy along them. The basic idea behind our routing selecting algorithm is that when all nodes in all possible paths have sufficient residual energy, a path with minimum total transmission energy among these paths is chosen and if all paths have nodes with low energy, max-min residual energy path is chosen, which tries to strike a balance between the minimum transmission energy and the energy consumption equivalence. The label switching technique is used to route the reinforcement messages to the source, which avoids the overhead of transmitting all nodes identifiers along the path. Simulation results show that SR-DD outperforms DD in uniform energy utilization.
INTRODUCTION
Driven by advances in MEMS micro-sensors, wireless networking and embedded processing, Wireless Sensor Networks (WSN) with limited computing and wireless communication capabilities are becoming increasingly available for commercial and military applications. The WSN have the advantages of fault tolerance, easy deployment and accurate sensing, which can be applied in many fields, such as battlefield surveillance, environment monitoring, industrial sensing and diagnostics, critical infrastructure protection and biological detection (Akyildiz et al., 2002).
The wireless senor networks have been hot research area at recent years, in which information aggregation and data routing with low energy consumption become an important research area. Since the sensor networks often work in the unattended circumstance, where battery replacement is impossible, it is very important to extend the lifetime of the wireless sensor network. The nodes have to use all kinds of energy-saving methods to decrease the energy consumption and prolong the longevity of the sensor network. So how to decrease the energy consumption of the nodes and how to prolong the lifetime of WSN are critical problems which should be considered first.
Some routing protocols have been proposed for Ad-Hoc network (Royer and Toh, 1999). But these protocols defined for wireless ad hoc networks are not well suited for WSN because what they take into account firstly is not energy consumption, so these research results can not be applied to WSN directly. Further researches have to be done in order to utilizing energy more efficiently.
The energy of a sensor node is consumed mainly by wireless transceiver, computing component and sensor, in which the wireless transceiver uses the most energy, so it is the most effective for energy-saving to decrease the data traffic. Many existing routing protocol are designed based on this principle. In SPIN (Kulik et al., 2002), nodes assign a high-level descriptor to completely describe their collected data (called meta-data) and perform meta-data negotiations before any data is transmitted. This assures that there is no redundant data sent throughout the network. Directed Diffusion (DD) (Intanagonwiwat et al., 2003), the most well known data dissemination protocol, where a sink queries the sensors in an on-demand fashion by disseminating an interest, i.e., a list of attribute-value pairs for the desired data, in order to build reverse paths from all potential sensing sources to the sink. This reverse path vector is named a “gradient”. By utilizing interest and gradients, paths are established between sink and sources. LEACH introduces the hierarchical clustering idea into sensor networks (Heinzelmam et al., 2000). It organizes the cluster dynamically using distributed algorithm, in which the cluster header collects the data from other nodes in the cluster and then directly forwards the data to the sink.
DD (Intanaganwiwt et al., 2003) is a flat routing protocol and extended to a data dissemination paradigm by (Silva et al., 2004), in which, the publish/subscribe mechanism provides an application’s view to a sensor network and attributed-based naming specifies which defines sources and sinks communicate and how intermediate nodes perform in-network processing. Sinks send interest messages to find sources; then, sources use exploratory data messages to reply to sinks. Sinks use positive and negative reinforcement messages to select or prune the path.
DD can be extended in many aspects, for example, geographic information in GPSR (Krap and Kuug, 2000), GEAR (Yu et al., 2001) and reliability support in RMST (Stann and Heidemann, 2003). It, however, still has some missing points such as global energy balancing, etc. In DD, the path reinforcement messages incline to choose “the shortest path”, along which the data can be transmitted from sources to the sink rapidly. But this kind of routing choice only cares for energy-saving, energy equivalence of the whole sensor network is not considered. It is possible for several data flows to share the same nodes (Pearlman and Haas, 1999), which forms the “hotspot”. The nodes lying in the “hotspot” are drained out of their energy quickly due to transmitting continually, while other nodes in the network have plenty of energy. That results in the network partition and reduces the longevity of the senor network.
To spread the network traffic in a more uniform fashion, this paper presents a source routing Directed Diffusion (SR-DD), which is another extension (or improvement) in Directed Diffusion. SR-DD chooses path based on the residual energy in the nodes, which avoids forming the “hotspot”.
SR-DD PROTOCOL
There are two assumptions have to be followed when designing SR-DD.
| • | There are enough computing and memory capabilities in the sink node |
| • | Each node has several neighbors |
The sink acts as a special role in the general WSN architecture. All the data have been sent to the sink and it has to be in charge of data aggregation. Meanwhile, it is also a gateway connecting the WSN with other networks, such as Internet, through satellite link. The sink must have enough energy, computing and storage capabilities. Otherwise, it can’t fulfill the complex work mentioned above. We make use of these capabilities of the sink and the overheads brought by improvement, such as storing correlative information and running path selecting algorithm, fall to it. Since the WSN have high density, there are often many neighbors for a node. So these assumptions are reasonable.
Directed diffusion overview: SR-DD is similar with DD, in which there are two phase process. The initial flooding of the interest, together with the flooding the exploratory data, constitutes the first phase; and the path reinforcement and the subsequent transmission of data along the reinforced path constitute the second phase (Silva et al., 2004). To describe the extension in DD clearly, we first state the original two-phase protocol-Directed Diffusion (DD).
In the first phase in DD, a sink sends interest messages to find sources and sources reply with exploratory data messages to maintain paths toward the sink. The sink broadcasts interest message through its neighbors. Interest message is transmitted hop-by-hop and is broadcasted by each node received it to its all neighbors. Each node received the interest caches it and builds an interest entry, which contains several gradient fields. Each gradient field presents a gradient that is a reply link to a neighbor from which the interest was received. At last, the interest messages diffuse throughout the whole network and the gradients are set up. On receipt of the initial data message from the source, each intermediate node marks the message as exploratory and forwards it to all neighbors for which it has matching gradients.
In the second phase in DD, the sink chooses a preferred neighbor to receive subsequent data messages for the same interest. To do this, the sink reinforces this preferred neighbor, which, in turn reinforces its preferred upstream neighbor and so on. After the initial exploratory data message, subsequent messages are sent only on reinforced paths.
Sr-DD protocol description: Since the exploratory data messages are transmitted along all the gradients with flooding, the same exploratory messages will be sent to the sink through different paths. In SR-DD, the exploratory message records routing information and the residual energy of the nodes when it travels the network. The nodes don’t forward the subsequent messages with the same identifiers after they have received an exploratory message.
| Table 1: | Routing of the exploratory messages |
| Fig. 1: | Sample topology |
In this way, the sink node can get a path from source to itself with correlative routing and energy information when it has received an exploratory message. These exploratory messages represent the complete different paths with the same source and sink-they have no common nodes. The sink node stores these paths with correlative energy information and then chooses a preferred path based on certain policy to send the path reinforcement messages. The subsequent sensing data will be transmitted along this path with a certain interval.
We present an example to explain how the exploratory messages reach the sink node in SR-DD routing protocol. In Fig. 1, node S denotes data source, node D denotes the sink node and other letters denote the intermediate nodes. The line between nodes means that two nodes connected by this line can communicate with each other directly. After an exploratory message sent by source node S reaches the node C, the same exploratory messages forwarded by other intermediate nodes, such as node M or A, have to be dropped. The node C forwards this exploratory message to the sink node D. A path from source to sink has been identified and stored by the sink for subsequent path selecting. Other paths have been identified by the same method. Finally, there are three paths (SCD, SMND and SABD) can be found by the sink node D, which is shown in Table 1.
There are no common nodes shared among different paths due to using the forwarding policy of exploratory messages described above, which avoids excess energy consumption in these common nodes.
Path selecting: The sink node extracts the routing and residual energy information from the received exploratory messages, selects proper path through path selecting algorithm and sends path reinforcement message along the chosen path. Selecting path depends on the residual energy on these paths. The path with the minimum energy consumption should be chosen if we expect to decrease the energy consumption of the whole WSN, while the path with the maximum residual energy should be chosen if we prefer energy equivalence. There exists conflict between two methods and we try to strike a balance between them.
The different paths starting from the same source are represented by a set Spath.
Spath = {P1, P2, ..., Pn}
Each element Pi(1≤i≤n) in Spath can be represented a sequence
<Vi1, Ei1>, <Vi2, Ei2>, ..., <Vik, Eik>
where Vij (1≤j≤k) denotes the node that has j hops from source node S in the path Pi, Eij (1≤j≤k) denotes the residual energy of node Vij and Vik denotes the neighbor of the sink node D. In SR-DD, the sink node needs to compute some values as follows:
(1) The residual energy Eimin of the minimum energy node in the path Pi (1≤i≤n).
| (1) |
(2) The residual energy sum Eisum of all the nodes in the path Pi (1≤i≤n).
| (2) |
We can construct a path set Apath, in which the minimum residual energy of each path (Eimin) is greater than a threshold Ethre.
| (3) |
The path selecting algorithm in SR-DD is described as follows:
| 1. | If Apath ≠Φ, the path with minimum Eisum (1≤i≤n) is chosen from Apath. |
| 2. | If Apath = Φ, the path with maximum Eimin (1≤i≤n) is chosen. |
SR-DD OPTIMIZATION
Optimizing energy information transmission: The path selecting algorithm described above relates to only two values, Eimin and Eisum, which doesn’t need the energy information of every node along the path. So we can optimize the implement of SR-DD. There is no need for the exploratory message to store the energy information of every node along the path. On the contrary, it only carries Eimin and Eisum, which have to be renewed at each node along the path. When the exploratory message travels down the path, the Eimin carried by the exploratory message will be replaced by the less residual energy value and the residual energy value of each node will be added to the Eisum.
Optimizing routing information transmission: SR-DD doesn’t define the details about how the path reinforcement messages are forwarded to the source. Our implement of SR-DD introduces the idea of label switching, which avoids storing all the node identifiers along the path. There is a label switching table maintained in each sensor node. Each record entry in this table can be represented as <Tag1, NextHop, Tag2>, where Tag1 denotes the local label assigned for the new received exploratory message, NextHop denotes the neighbor node from which the exploratory message was received and Tag2 denotes the label carried by the exploratory message. We take the path SABD (Fig. 1) as example to describe the label switching process.
Figure 2 shows this label switching process. When the source node S sends an exploratory message, it chooses a unused local label s1, places s1 into the head of this exploratory message and sends to neighbor A. After node A has received this exploratory message, it extracts the label s1, chooses a unused local label a1, builds a record <a1, S, s1> and inserts this record into the label switching table. Meanwhile, the node A replaces the current label s1 in the exploratory message with label a1 and sends the message to neighbor B. The process in node B is similar to that in node A. That is to say, node B replaces label a1 in the exploratory message with label b1 and sends to the sink node D. At that time, the sink D gets a path along which the sensing data can reach this sink. The sink identifies this path with label P1, builds a record <P1, B, b1> and inserts it into the path table.
| Fig. 2: | Example of label switching |
By the way, the path table in the sink is an extended label switching table, which also contains Eimin and Eisum for path selecting.
As soon as a path has been chosen, such as P1, the sink node finds the record <P1, B, b1> indexed by label P1, builds a path reinforcement message, places the label b1 into this message and sends the message to neighbor B. After node B has received this reinforcement message, it extracts the label b1, finds the record <b1, A, a1> indexed by label b1 in the local label switching table, replaces the label b1 in the reinforcement message with label as1 and sends to neighbor A. The subsequent progresses are similar to this, until this reinforcement message reaches the source node S.
SR-DD IMPLEMENTATION
Based on optimization analysis described above, three new fields, the minimum residual energy Emin, the energy sum of all the nodes Esum in a path and the label, will be appended to the head of the exploratory message (Fig. 3a).
When the exploratory messages travel through the sensor network, each node who has received the message first examines whether this message with the same identifier has been processed. If it has been processed, this message will be dropped; and if not, some fields in the head of this message will be modified. First, the label is extracted from the label field in the message and a new local allocated label is placed in the same label field. A new record entry is built based on this new local allocated label, the old label extracted from the exploratory message and the neighbor node from which the exploratory message was received and inserted into the label switching table. Second, the value of the minimum residual energy field Emin is extracted and compared with local residual energy of this node. If local residual energy value is less than the value of Emin carried by the exploratory message, it will replace the current value of Emin field in the message.
| Fig. 3: | Modified message structure. (a) exploratory (b) reinforcement |
Third, the local residual energy value will be added into the value extracted from the Esum field in this exploratory message and the new value is placed into the Esum field. Finally, the modified exploratory message is sent to all neighbors for which it has matching gradients.
There is only one field, label, to be appended to the path reinforcement message, whose purpose is to direct the path reinforcement message to the source (Fig. 3b).
The node who has received a reinforcement message extracts the label from the head of this packet. Indexed with this label, a record entry is found out from the local label switching table. The next neighbor node to which this reinforcement message will be sent and a new next hop label are gained. The old label will be replaced by this new label and put into the label field of the path reinforcement message. Finally, this modified reinforcement message will be sent to the specified neighbor node.
There is only several bytes increment in the packet size due to modifying message structure. The overhead for transmitting the new message is so small that it can be ignored.
The process in usual sensor nodes include operating the label switching table and switching label in the message. Comparing with original process, the overhead incurred by these processes is small. The usual sensor nodes have to maintain a label switching table, which consumes certain memory resource. Each entry in the label switching table associates with a timeout value. If no reinforcement message has been received during the timeout, the entry will be erased from the label switching table.
The sink node is in charge of running path selecting algorithm. It also maintains a extended label switching table, in which two fields, Emin and Esum, have been appended to each entry. Choosing path will depend on these information.
SIMULATION AND ANALYSIS
We have implemented SR-DD based on the code of Diffusion in the ns-2 simulator. A network of 289 nodes in a square area of 500x500 m was simulated, where the transmission range of a sensor node is 40 m. One source and one sink have been chosen to simulate the traffic. Sink is selected at the upper left corner and source is located at the bottom right corner. The source sends data packet whose size is 128 bytes at the interval of 0.5 sec. The sink generates interest message whose size is 64 bytes at the interval of 600 sec.
| Fig. 4: | Comparison of energy consumption distribution. The initial
energy of each node is set to 1000J and the simulation stop time is set
to 10000s. (a) DD. (b) SR-DD |
The ns-2 simulator implements a 2 Mb/s 802.11MAC layer. To more closely mimic realistic sensor network radios, we altered the ns-2 radio energy model such that the idle-time power dissipation was about 0.035 W, or nearly 10% of its receive power dissipation (0.395 W) and about 5% of its transmit power dissipation (0.660 W).
The design goal of SR-DD is to achieve the balance of energy consumption among nodes, so we compare the energy consumption distribution in SR-DD and DD.
The result is shown in Fig. 4, which shows that the energy consumption of the nodes in the shortest path from source to sink is much higher than those in other paths in DD, while there is more uniform energy utilization in SR-DD. The shortest path routing could give high throughput with minimum response time, but nodes lying on this path are drained out of their energy too quickly.
| Fig. 5: | Comparison of average delay |
Although most of the nodes in the network have plenty of energy, they are no longer connected with each other due to random concentration of dead nodes (with zero battery power) in the network. The packets will be dropped due to disconnected routes. SR-DD avoids this problem with more uniform energy utilization.
Figure 5 plots the average delay observed as a function of network size, which shows that SR-DD incurs little additional average delay compared with original DD.
CONCLUSIONS
This study proposes a source routing Directed Diffusion (SR-DD), which is an improved Directed Diffusion, in order to avoid “hotspot” in the wireless sensor networks. The sink node makes a choice in different paths based on the residual energy of nodes in these paths. The Choice considers the energy consumption both in the whole network and in the local area, which achieves the energy balance of the network. In the implement of SR-DD, the idea of label switching is introduced to avoid storing all node identifiers along the path, which reduces the overhead of transmitting information for path selecting to much low level. The simulation result shows that SR-DD avoids the nodes in “hotspot” depleting energy while other nodes perhaps have much residual energy. SR-DD outperforms Directed Diffusion in uniform energy utilization.