Routing is an essential operation in wireless sensor networks. Most existing routing protocols are designed for homogeneous sensor networks. Recent studies show that a homogeneous sensor network has a poor fundamental performance limit. To achieve better performance, we adopt a Heterogeneous Sensor Network (HSN) model. In this paper, we present an efficient NEar-optiMal rOuting (NEMO) protocol for HSNs. We evaluate the performance of NEMO through extensive simulation experiments. Our results show that NEMO can find near-optimal routes in an HSN and has very small overhead.

Robustness and reliability are critical issues in network management. To provide resiliency, a popular protection scheme against network failures is the simultaneous routing along multiple disjoint paths. Most previous protection and restoration schemes were designed for all-or-nothing protection and thus, an overkill for data traffic. In this work, we study the Reliable Adaptive Multipath Provisioning (RAMP) problem with reliability and differential delay constraints. We aim to route the connections in a manner such that link failure does not shut down the entire stream but allows a continuing flow for a significant portion of the traffic along multiple (not necessary disjoint) paths, allowing the whole network to carry sufficient traffic even when link/node failure occurs. The flexibility enabled by a multipath scheme has the tradeoff of differential delay among the diversely routed paths. This requires increased memory in the destination node in order to buffer the traffic until the data arrives on all the paths. Increased buffer size will raise the network element cost and could cause buffer overflow and data corruption. Therefore, differential delay between the multiple paths should be bounded by containing the delay of a path in a range. We first prove that RAMP is an NP-hard problem. Then we present a pseudo-polynomial time solution to solve a special case of RAMP, representing edge delays as integers. Next, an (1 + e)-approximation algorithm is proposed to solve the optimization version of the RAMP problem. An efficient heuristic is also provided for the RAMP problem. We also present numerical results confirming the advantage of our schemes as the first solution for the RAMP problem.