Heat-Diffusion (HD) routing is our recently-developed queue-aware routing policy for multi-hop wireless networks inspired by Thermodynamics. In the prior theoretical studies, we have shown that HD routing guarantees throughput optimality, minimizes a quadratic routing cost, minimizes queue congestion on the network, and provides a trade-off between routing cost and queueing delay that is Pareto-Optimal. While striking, these guarantees are based on idealized assumptions (including global synchronization, centralized control, and infinite buffers) and heretofore have only been evaluated through simplified numerical simulations. We present here the first practical decentralized Heat-Diffusion Collection Protocol (HDCP) for wireless sensor networks and detail its implementation on Contiki OS. We present a thorough evaluation of HDCP based on real testbed experiments, including a comparative analysis of its performance with respect to the state of the art Collection Tree Protocol (CTP) and Backpressure Collection Protocol (BCP) for wireless sensor networks. We find that HDCP has a significantly higher throughput region and greater resilience to interference compared to CTP. However, we also find that the best performance of HDCP is comparable to the best performance of BCP, due to the similarity in their neighbor rankings, which we verify through a Kendall's-Tau test.
Besides BCP, there are a number of other prior works on routing and collection protocols for wireless sensor networks, including the Collection Tree Protocol (CTP) @cite_9 , Glossy @cite_7 , Dozer @cite_19 , Low-power Wireless Bus @cite_0 , ORW @cite_8 and Oppcast @cite_15 . We provide a side by side comparison of HDCP with the well-known CTP and BCP protocols. We believe this provides a meaningful comparison with a state of the art minimum cost quasi-static routing protocol as well as a state of the art queue and cost-aware dynamic routing protocol.
@cite_7 @cite_8 @cite_9 @cite_0 @cite_19 @cite_15
2102482985 2160343401 1481321196 2150050284
Current data collection protocols for wireless sensor networks are mostly based on quasi-static minimum-cost routing trees. We consider an alternative, highly-agile approach called backpressure routing, in which routing and forwarding decisions are made on a per-packet basis. Although there is a considerable theoretical literature on backpressure routing, it has not been implemented on practical systems to date due to concerns about packet looping, the effect of link losses, large packet delays, and scalability. Addressing these concerns, we present the Backpressure Collection Protocol (BCP) for sensor networks, the first ever implementation of dynamic backpressure routing in wireless networks. In particular, we demonstrate for the first time that replacing the traditional FIFO queue service in backpressure routing with LIFO queues reduces the average end-to-end packet delays for delivered packets drastically (75 under high load, 98 under low load). Further, we improve backpressure scalability by introducing a new concept of floating queues into the backpressure framework. Under static network settings, BCP shows a more than 60 improvement in max-min rate over the state of the art Collection Tree Protocol (CTP). We also empirically demonstrate the superior delivery performance of BCP in highly dynamic network settings, including conditions of extreme external interference and highly mobile sinks. This paper presents and evaluates two principles for wireless routing protocols. The first is datapath validation: data traffic quickly discovers and fixes routing inconsistencies. The second is adaptive beaconing: extending the Trickle algorithm to routing control traffic reduces route repair latency and sends fewer beacons. We evaluate datapath validation and adaptive beaconing in CTP Noe, a sensor network tree collection protocol. We use 12 different testbeds ranging in size from 20--310 nodes, comprising seven platforms, and six different link layers, on both interference-free and interference-prone channels. In all cases, CTP Noe delivers > 90 of packets. Many experiments achieve 99.9 . Compared to standard beaconing, CTP Noe sends 73 fewer beacons while reducing topology repair latency by 99.8 . Finally, when using low-power link layers, CTP Noe has duty cycles of 3 while supporting aggregate loads of 30 packets minute. Sensor networks are wireless adhoc networks where all the nodes cooperate for routing messages in the absence of a fixed infrastructure. Non-flooding, guaranteed delivery routing protocols are preferred because sensor networks have limited battery life. Location aware routing protocols are good candidates for sensor network applications, nevertheless they need either an external location service like GPS or Galileo (which are bulky, energy consuming devices) or internal location services providing non-unique virtual coordinates leading to low delivery rates. In this paper we introduce Position Trees a collision free, distributed labeling algorithm based on hop counting, which embed a spanning tree of the underlying network. The Routing with Position Trees (RTP) is a guaranteed delivery, non-flooding, efficient implicit routing protocol based on Position Trees. We study experimentally the statistical properties of memory requirements and the routing efficiency of the RPT. As a specific area of sensor networks, wireless in-home sensor networks differ from general sensor networks in that the network has nodes with heterogeneous resources and dissimilar mobility attributes. For example, sensor with different radio coverage, energy capacity, and processing capabilities are deployed, and some of the sensors are mobile and others are fixed in position. The architecture and routing protocol for this type of heterogeneous sensor networks must be based on the resources and characteristics of their member nodes. In addition, the sole stress on energy efficiency for performance measurement is not sufficient. System lifetime is more important in this case. We propose a hub-spoke network topology that is adaptively formed according to the resources of its members. A protocol named resource oriented protocol (ROP) was developed to build the network topology. This protocol principally divides the network operation into two phases. In the topology formation phase, nodes report their available resource characteristics, based on which network architecture is optimally built. We stress that due to the existence of nodes with limitless resources, a top-down appointment process can build the architecture with minimum resource consumption of ordinary nodes. In the topology update phase, mobile sensors and isolated sensors are accepted into the network with an optimal balance of resources. To avoid overhead of periodic route updates, we use a reactive strategy to maintain route cache. Simulation results show that the hub-spoke topology built by ROP can achieve much longer system lifetime.