Research Article
 

GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks



Jiming Chen, Jialu Fan, Xianghui Cao and Yousian Sun
 
Facebook Twitter Digg Reddit Linkedin StumbleUpon E-mail
ABSTRACT

In this research, a Greedy Rumor Forwarding Routing (GRFR) protocol is proposed for Wireless Sensor/Actor Networks (WSANs) based on geographic information, which improves rumor routing protocol. The study explores the performance of GRFR including both the network lifetime and communication delay at two different system architectures based on the software simulation platform SensorSimulator, which is a discrete event simulation framework for the networks built over OMNeT++. Furthermore, it is deeply investigated how the sensor nodes within one hop from the sink affect the network lifetime.

Services
Related Articles in ASCI
Search in Google Scholar
View Citation
Report Citation

 
  How to cite this article:

Jiming Chen, Jialu Fan, Xianghui Cao and Yousian Sun, 2008. GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks. Information Technology Journal, 7: 661-666.

DOI: 10.3923/itj.2008.661.666

URL: https://scialert.net/abstract/?doi=itj.2008.661.666
 

INTRODUCTION

Wireless Sensor Networks (WSNs) promise an unprecedented fine-grained interface between the virtual and physical world (Akyildiz et al., 2007). They are one of the most rapidly developing new information technologies, with potential applications in a wide range of fields including industrial process control, security and surveillance, environmental sensing and structural health monitoring, etc. Although having wide applications, WSNs only realize the functions of data collection and transmission, which still are open-loop from viewpoint of control system designers. The wireless sensor/actor networks (WSANs), which is an entirely new technology, has been sprung up for the last few years based on WSNs (Akyildiz and Kasimoglu, 2004). WSANs are capable of not only observing the physical world, processing the data, but also making decisions based on the observations and performing appropriate actions. In WSANs, actors take actions onto the observed object based on the sensory data, by which way to construct the real closed-loop feedback control and automatic systems. This network can be an integral part of systems such as battle field surveillance and microclimate control in buildings, nuclear, biological and chemical attack detection, home automation and environmental monitoring (Chen et al., 2007).

As we know, efficient bandwidth utilization and quality of service are mostly considered in traditional wireless network design. In WSAN however, sensor nodes are deployed in the region of interest, where it is impractical or infeasible for humans to interact with or monitor them, thus unattended. In this case, how to maximize the network lifetime with constrained resource becomes complex and crucial. Besides, in some scenarios such as fire suppression, the communication traffic is typically delay-sensitive. Therefore, supporting a real-time communication is critical in the application of WSANs. There are mainly two typical kinds of physical system architecture of WSANs (Chaudhry et al., 2006), namely, autonomic architecture (AA) and centralized architecture (CA), which will also be described further. Our goal is mainly to design a routing for WSANs that contributes to transfer sensory data to the distributed actors, solving the problem which sensors communicate with which actors? and comparing the performance of AA with that of CA under the same circumstances. Apparently, applying the system architecture with better performance such as longer network lifetime and smaller communication delay to industry will be more productive with the same devotion.

WSANs characterize rigorous real-time requirement of coordination and communication. Although, many protocols and algorithms have been proposed for WSNs in recent years, they may not be well-suited for WSANs because of the different requirement of WSANs. Many recently developed protocols for WSANs are also under primary steps. For example, in Conti et al. (2004), only actor-actor coordination is handled without any insight into the sensor-actor coordination problem. Some recent studies (He et al., 2003; Felemban et al., 2005) have considered the issue of real-time communication in sensor networks. A protocol is also introduced in (Krotkov and Blitch, 2004) where it is assumed that sensor and actor nodes are of same type which obviously does not reflect the actual WSANs. In Vedantham et al. (2006), the problem of hazards is considered, which consist of the out-of-order execution of queries and commands resulting from a lack of coordination between sensors and actors. However, coordination problems in sensor-actor or in actor-actor communications are not considered in the study.

Introducing distributed multi-actor to WSNs causes big challenges in designing a new communication paradigm, much different from the centralized architecture in WSNs. This research will deal with the principle problems about sensor-actor communication in the WSANs and evaluate the proposed routing by extensive simulation experiments.

SYSTEM MODEL OF WSAN

In Akyildiz and Kasimoglu (2004) sensor nodes collect data from the environment while actors perform appropriate actions based on this data, respectively. Sensor nodes detecting a phenomenon can transmit their readings to the actor nodes which take appropriate actions, or route data back to the sink which may control actors. The former case is named as AA due to the nonexistence of central controller while the latter case is defined as CA since the sink (central controller) collects data and coordinates the acting process. These two architectures are given in Fig. 1.

Image for - GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks
Fig. 1: Two architectures for WSAN

The advantage of CA attributes to its topology, which is similar to the architecture of the well-known WSNs. The community of WSNs researchers has proposed, implemented and measured a variety of routing algorithms for such networks which could be directly applied for CA form of WSANs. In contrast, AA naturally decomposes a large network into separate zones within which data processing and aggregation can be performed locally. Because WSANs have some particular characteristics due to the coexistence of sensors and actors, there are many challenges have to be investigated. The principal problem, that transfers sensory data from sensors to actors, should be solved. A suitable and effective routing should be designed for WSANs. Further a new routing protocol is developed, which is well-suited for AA as well as CA.

GREEDY RUMOR FORWARDING ROUTING PROTOCOL FOR WSAN

Depending on the application, the routing protocol suitable for WSANs should be a kind of event driven and geography based routing protocol. It is shown that geographic routing allows routers to be nearly stateless and requires propagation of topology information for only a single hop: each node needs only the knowledge of its neighbors` locations. The location of a packet`s destination and locations of the next hop candidates are information sufficient to make correct forwarding decisions without any other topological information.

Here, GRFR protocol is proposed, an improved rumor routing protocol, for routing sensory data from any sensor to its destination (actor) in WSANs. Rumor routing protocol is a kind of query mechanism (Braginsky and Estrin, 2002). The query nodes have to diffuse queries to the whole network, which consumes too much energy. GRFR improves rumor routing protocol to a kind of event driven and geographic routing protocol, as mentioned above, which is well-suited for both AA and CA. GRFR mainly includes three parts as discussed below.

Selection of the source sensor and destination actor: In WSANs, it is assumed that distributed actors can self-localized and broadcast their position over the network. Even if the actors are mobile, their location will be broadcasted after they reach a new position. Each sensor will maintain a location table for the actors.

To make it simple, we assumed the event is a vertex with circular affecting range in the whole network topology. The network will elect source node and destination node when an event appears. An event triggers the sensors within its influencing scope, which then communicate mutually to elect one source node.

Image for - GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks
Fig. 2: Example of election of source and destination nodes

Normally, the nearest and available sensor to the event will be elected to the source node. However, the election of destination node in AA differs from the one in CA, which attributes to the coexistence of sensors and actors. The nearest actor in the actor list in the table to the event will be elected to the destination node in AA. In contrast, the sink is the destination node all the time in CA. So in AA, the routing is dynamic and can not be maintained by routing table in each sensor, especially with mobile actors. But CA can construct a relatively static routing path comparing with AA. That`s why traditional research work on WSNs should be improved.

An example of election of the source and destination nodes in AA is shown in Fig. 2. When an event happens, the sensor nodes within its influencing scope all detect the event and they communicate with each other to elect Node 0 as the source node, since Node 0 is the closest sensor node to the event vertex. Then Node 0 will find the nearest actor in its actor table as the destination node because the actors` locations are known to all the sensor nodes by initially broadcasting over the network. Finally, the nearest actor to the event vertex, actor node 4, will be chosen as the destination node.

As introduced above, there is only one node elected as the source node among all the nodes detected the event information. That is because if the nodes within the influencing scope all relay the packets, it is likely that more than one actor node being triggered and the actor nodes must communicate and coordinate with each other and the actor-actor coordination is beyond the research domain of this paper. Therefore, in order to simplify the problem, without loss of generality, we assume only one node sensed the phenomena and confine the election of source nodes to the above condition.

Image for - GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks
Fig. 3: Example of greedy rumor forwarding routing

Routing algorithm: In order to transmit the packet from source sensor node to destination node, an event driven and geographic routing algorithm is required. Therefore, GRFR algorithm is proposed, with which packets are marked by their originators with their locations of destinations. As a result, a forwarding node can make a greedy choice in choosing a packet`s next hop. We assume in this work that all wireless sensor nodes know their neighbors. We consider topologies where the wireless nodes are roughly in a plane. Specifically, the greedy choice of next hop is geographically closer to the packet`s destination than the current node. Furthermore, what rumor means is that if more than one nodes accord with the above condition, there will be a random one to forward the packet further, i.e., they have the equal priorities. Forwarding in this regime follows successively closer geographic hops, until the destination is reached.

An example of next hop choice in GRFR algorithm is given in Fig. 3. Here, Node 0 receives a packet destined for D. Node 0`s radio range is denoted by the dotted circle about Node 0 and the arc with radius equal to the distance between Node 0 and D is shown as the dashed arc about D. From Node 1 to Node 4 all have equal priorities to be the next hop. This GRFR process repeats, until the packet reaches D.

TTL information in GRFR protocol: TTL, abbreviating for Time to Live, a field in the Internet Protocol (IP) that specifies how many hops a packet can travel before being discarded or returned. TTL contained in every packet is another important attribute of GRFR. The TTL, a constant, will be added in every packet when it generates and is decremented with transmitting. The packet is forwarded if the TTL is greater than zero and the sensor nodes will discard a packet whose TTL is zero. The packets without TTL may cause routing loops in the network.

SIMULATION EVALUATION

Simulation environment: The performance of GRFR is evaluated in the two system architectures based on OMNeT++ (http://www.omnet.org), objective Modular Network Test-bed in C++, which is a public-source, component-based, modular and open-architecture simulation environment with strong GUI support and an embeddable simulation kernel. Its primary application area is the simulation of communication networks, but because of its generic and flexible architecture, it has been successfully used in other areas. Recently, many discussion groups propose electing OMNeT++ to the uniform tool for the algorithm design and analysis in WSNs. So far, there are two simulation frameworks, EYES Simulation Framework (http://wwwes.cs.utwente.nl/ewsnsim/) and SensorSimulator (Iaquinto et al., 2008), built over OMNeT++. We use the software OMNeT++ and SensorSimulator to investigate the quality of service of GRFR under the structure of both AA and CA.

In the simulation experiments where we compare the performance of AA with the one of CA, simulation parameters is identical to a subset of those used in Mica2, which is a third generation mote module used for enabling low-power, wireless, sensor networks (http://www.xbow.com). The concrete simulation topological parameters are shown in Table 1. However, they only differ from the existence of a sink, which characterizes the CA of WSANs.

Performance evaluations: As presented above, simulation experiments are designed to evaluate the performance of GRFR with AA and CA. In this study, quality of service of GRFR for WSANs is investigated including two main parts: network lifetime and communication delay. Furthermore, the paper also designs an experiment to analyze how the sensor nodes within one hop from the sink affect the network lifetime.

Network lifetime of AA vs. CA: The sensor node exhausting its own energy is always considered as node failure. Incidentally, in the simulation, when the remainder energy of a sensor node is less than or equal to 0.001, it is thought to be failure. The network lifetime is defined as either the time of the first node (Chang and Tassiulas, 2004; Madan and Lall, 2006; Seo et al., 2007; Kalpakis et al., 2003) or a certain percentage nodes failure (Duarte-Melo et al., 2005; Cheng et al., 2008). The former is pessimistic because the remainder nodes can also fulfill appropriate tasks and the latter is flexible because we can choose the percentage according as the applications.

Table 1: Detailed simulation setting of AA/CA
Image for - GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks

Image for - GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks
Fig. 4: Failure time of partial nodes in AA vs CA adopting GRFR in WSANs

In our simulation, the positions of the sensor nodes are stationary that do not move anymore after once deployed and their radio radius are constant. Thus, the network cannot work, as there are only half sensor nodes alive. Our simulations are for networks of 100 nodes, so the failure time of 12510203040 and 50 nodes is recorded and compared in AA with CA and Fig. 4 shows the results.

Apparently, as shown in Fig. 4, the failure time points at 50 nodes in AA are all greater than that of CA. Thus, we can conclude that the AA have longer network lifetime than the CA with GRFR protocol under the same given circumstances. Specially, the maximum difference of the networks lifetime with AA and CA appears at the time when 10 nodes fail. As a matter of fact, our simulated networks are quite dense and there is an average of approximately 10 neighbors within range of the average node in these networks. The relationship will be particularly analyzed as below:

From the different physical architectures of both AA and CA, it is obvious that the lifetime of the sensor nodes which are within one hop from the destination nodes will affect the network lifetime. We design an experiment to illustrate the phenomenon.

In the initialized files, we assign each sensor in the network a unique identifier from 0 to 99. Node 99 is the sink in CA and from Node 95 to Node 99 are 5 actors in AA. Due to the random-seed are both equal to 1, the deployments of the two architectures are identical. In other words, the nodes with the same identifiers have the same coordinates. Hence, the same nodes have the same neighbors in the two architectures.

Table 2: Neighbor lists of destination nodes
Image for - GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks

Table 3: Former 20/10 Failure NodeID in WSANs with AA/CA
Image for - GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks

The neighbor lists of Node 95 to Node 99 are shown in Table 2 and 3 lists the former 20/10 failure node identifiers in AA and CA, respectively.

Comparing Table 2 with Table 3, it can be found that there are 9 neighbor nodes of the sink in the former 10 failure nodes in CA and the former 20 failure nodes are all the neighbor nodes of the 5 actors in AA.

From the high percentage, it can be concluded that the lifetime of nodes within one hop from the destination nodes is shorter than that of the other nodes in the network, which will be expound as follows. In CA, wherever the event occurs, event information always passes through the sensor nodes within one hop from the sink. Thus, those sensor nodes have excessive burden of relaying. When these nodes fail, the connectivity can be lost and the network will be out of work and become useless. However, in AA, it is much more likely that for each event different actors may be triggered. This implies that the relay load gets evenly distributed between all nodes. As presented in the simulation results, there is an average of approximately 10 neighbors within range of the average node in the networks and the nodes within one hop from the sink nodes may fail faster than other nodes. Thus, the time of 10 nodes failure may be considered as the lifetime of CA. Where, the relaying sensor nodes in AA are also different for each event because of the existence of 5 actors, we can consider the time of 50 nodes failure as the lifetime of network with AA. As shown in Fig. 4, the difference of the lifetime of network between AA and CA is obvious. The above data manifests the superior of AA over CA in WSANs.

Analysis of delay in WSANs: Depending on the application there may be a need to rapidly respond to accident event. Thus, it may request a low communication delay in the data transmission and we also design an experiment that manifests the superiority of AA over CA, which will be interpreted below.

As presented in the introduction, WSANs have two rigorous requirements: real-time and coordination.

Image for - GRFR: Greedy Rumor Forwarding Routing for Wireless Sensor/Actor Networks
Fig. 5: Failure time of partial nodes in AA vs CA adopting GRFR in WSANs

We discuss the sensor-actor coordination in the protocol design. Then, the real-time characteristic is investigated. The most important characteristic of sensor-actor communication is to provide low communication delay due to the proximity of sensors and actors. In some applications such as in fire, the communication traffic is typically delay-sensitive. Therefore, supporting a real-time traffic is more crucial in the application of WSANs.

Above all, an experiment is designed to compare the communication latency between AA and CA in WSANs. In the simulation, we gain the hops of packet transmission from source nodes to destination nodes in every event transmission and we choose 20 pairs uniformly, as shown in Fig. 5. As in Fig. 5, the hops of packet transmission in AA are almost all smaller than the ones in CA. That is because the sensed information is conveyed from sensors to actors in AA, since they may be close to each other as shown in Fig. 2. As a result, the latency is minimized in AA. Moreover, in AA since event information is transmitted locally through sensor nodes around the event area, sensors that are far from the event area do not function as relaying nodes, which savings network resources in AA.

CONCLUSIONS

In this study, GRFR protocol for WSANs is proposed and presented in detail, which solves the key problem of data transmission from sensors to actors in distributed environment with multi-actors. The benefits of GRFR partially stem from geographic routing algorithm using only immediate-neighbor information in forwarding decisions. Then, the performances of WSANs with two architectures, i.e., CA and AA, are evaluated using the software SensorSimulator, which is a discrete event simulation framework for sensor networks built over OMNeT++. The simulation results obviously manifest the superiority of AA over CA in terms of utilizing distributed sensor nodes for information sensing, transmission and action making. Furthermore, this paper analyzes how the sensor nodes within one hop from the sink affect the network lifetime.

It is concluded from experiment results that in CA, the nodes near the sink have a higher load of relaying packets, which makes the network`s lifetime shorter. In contrast, the relay load are distributed among all nodes in AA, though there exits the same problem with the nodes around the actors. As sensors and actors go close to each other, the communication latency may become much lower in AA.

In our future research, more attention will be paid on actor/actor coordination before any specific action is to be taken. Controller design for actors will also be our important research area.

ACKNOWLEDGMENTS

This research is supported by Joint Funds of NSFC-Guangdong under grants U0735003; Natural Science Foundation of China under grants No. 60604029, 60702081; Natural Science Foundation of Zhejiang Province under grants No. Y106384; the Science and Technology Project of Zhejiang Province under grants No. 2007C31038 and the Scientific Research Fund of Zhejiang Provincial Education Department under grants No. 20061345.

REFERENCES

  1. Akyildiz, I.F. and I.H. Kasimoglu, 2004. Wireless sensor and actor networks: Research Challenges. Ad Hoc Networks, 2: 351-367.
    CrossRef  |  


  2. Akyildiz, I.F., T. Melodia and K.R. Chowdury, 2007. Wireless multimedia sensor networks: A survey. IEEE Wireless Commun., 14: 32-39.
    Direct Link  |  


  3. Braginsky, D. and D. Estrin, 2002. Rumor routing algorithm for sensor networks. Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications, September 28, 2002, Atlanta, Georgia, USA., pp: 22-31
    Direct Link  |  


  4. Chang, J. and L. Tassiulas, 2004. Maximum lifetime routing in wireless sensor networks. IEEE/ACM Trans. Network., 12: 609-619.
    CrossRef  |  Direct Link  |  


  5. Chaudhry, S.A., A.H. Akbar, F. Siddiqui and K.H. Kim, 2006. Autonomic network management for wireless mesh and MANETs. Proceedings of the Self-Organization Systems, 41: 259.


  6. Chen, M., S. Gonzalez and V. Leung, 2007. Applications and design issues for mobile agents in wireless sensor networks. IEEE Wireless Commun., 14: 20-26.
    Direct Link  |  


  7. Cheng, Z., M. Perillo and W.B. Heinzelman, 2008. General network lifetime and cost models for evaluating sensor network deployment strategies. IEEE Trans. Mobile Comput., 7: 484-497.
    CrossRef  |  


  8. Conti, M., G. Maselli, G. Turi and S. Giordano, 2004. Cross-layering in mobile ad hoc network design. Computer, 37: 48-51.
    CrossRef  |  Direct Link  |  


  9. Duarte-Melo, E., M. Liu and A. Misra, 2005. An efficient and robust computational framework for studying lifetime and information capacity in sensor networks. Mobile Networks Appl., 10: 811-824.
    Direct Link  |  


  10. Felemban, E., C.G. Lee, E. Ekici, R. Boder and S. Vural, 2005. Probabilistic QoS guarantee in reliability and timeliness domains in wireless sensor networks. Proceedings of the IEEE INFOCOM, Miami, March 13-17, 2005, Department of Electr. and Comput. Eng., Ohio State Univ., Columbus, OH, USA., pp: 2646-2657


  11. He, T., J. Stankovic, C. Lu and T. Abdelzaher, 2003. SPEED: A real-time routing protocol for sensor networks. Proceedings of the 23rd International Conference on Distributed Computing Systems, May 19-22, 2003, Providence, RI., USA., pp: 46-55
    CrossRef  |  


  12. Iaquinto, J., R.S. Adelaar and J.S. Wayne, 2008. Simulation of contact gait in the cadaveric lower extremity using a novel below knee simulator. Foot Ankle Int., 29: 66-71.
    Direct Link  |  


  13. Kalpakis, K., K. Dasgupta and P. Namjoshi, 2003. Efficient algorithms for maximum lifetime data gathering and aggregation in wireless sensor networks. Comput. Networks, 42: 697-716.
    CrossRef  |  Direct Link  |  


  14. Krotkov, E. and J. Blitch, 2004. The defense advanced research projects agency (DARPA) tactical mobile robotics program. Int. J. Roboti, 18: 769-776.
    CrossRef  |  


  15. Madan, R. and S. Lall, 2006. Distributed algorithms for maximum lifetime routing in wireless sensor networks. IEEE Trans. Wireless Commun., 5: 2185-2193.
    CrossRef  |  Direct Link  |  


  16. Seo, M., W. Choi, Y.S. Kim and J. Park, 2007. Lifetime prediction routing protocol for wireless sensor networks. IEICE. Trans. Commun., E90B: 3680-3681.
    Direct Link  |  


  17. Vedantham, R., Z. Zhuang and R. Sivakumar, 2006. Hazard avoidance in wireless sensor and actor networks. Comput. Commun. (Elsevier), 29: 2447-2736.
    Direct Link  |  


©  2022 Science Alert. All Rights Reserved