Time-Sensitive Utility-Based Single-Copy Routing in Low-Duty-Cycle Wireless Sensor Networks

Utility-based routing is a routing scheme based on a special composite utility metric. The existing utility-based routing algorithms have not yet considered the delivery delay, so that they cannot work well in low-duty-cycle wireless sensor networks (WSNs). In this paper, we present a time-sensitive utility model. A successful end-to-end message delivery will obtain a positive benefit, which linearly decreases along with an increasing delivery delay; otherwise, a failed delivery will receive zero benefit. The utility is the benefit minus the total transmission costs, no matter if the message delivery succeeds or fails. Such a utility model is analogous to the postal service in the real world. Under this novel utility model, we design two optimal time-sensitive utility-based routing algorithms for the non-retransmission setting and the retransmission-allowed setting, respectively. In our designs, we derive an iterative formula to compute the expected utility of each message delivery, and we present a binary search method to determine the optimal retransmission times. As a result, the two algorithms can achieve the optimal expected utility for each message delivery, which is the optimal balance among the concerned factors, including benefit, reliability, delay, and cost. The simulation results also prove the significant performances of our proposed algorithms.