Receiver-cost cognizant maximal lifetime routing in embedded networks: Model and solutions

Wireless ad hoc networks (WANET) feature flexible, scalable and low-cost wireless communication and enable revolutionary applications that would change our everyday life. Research that tackles the intrinsic energy constraints is key to WANET's success. Existing research is based on traditional wireless devices with large inter-node distances, where it is reasonable to assume the energy for transmitting packets dominates the overall energy consumption. However, as small form-factor and low-power devices with short-range communication capability have been widely adopted, receiving energy costs are comparable to transmitting costs. This thesis fills the gap by investigating the impact of receiving energy costs on maximal lifetime routing.;In this thesis, four receiving energy cost models are introduced, while taking into account the features of the transceiver circuits and underlying media access control protocol: Designated Constant (DCR), Overhearing Constant (OCR), Designated Adaptive (DAR) and Overhearing Adaptive (OAR). By re-examining a well-studied problem, maximal multicast lifetime routing, the study investigates the impact of receiving energy costs. The results suggest that receiving energy deserves explicit attention when energy efficient schemes are developed. Specifically, ignoring the impact of receiving cost leads to significant performance degradation and addressing the energy for receiving packets helps build significantly better routing algorithms.;Under the DCR model, an algorithm ignoring receiving costs may obtain 50% less than the optimal multicast lifetime. An optimal solution is proposed to construct a maximal-lifetime multicast tree. Under the OCR model, a solution which neglects receiving costs can perform O(n) times worse than the optimal. It is shown that the problem becomes NP-hard. A heuristic solution is proposed which considers the impact of overhearing costs explicitly. It is proved that NP-hardness remains under both DAR and DAR models. This research is extended by studying the impact of the node movement on the multicast lifetime in mobile ad hoc networks. The first distributed algorithm adaptive to the network dynamics is proposed. The correctness and effectiveness of the proposed approaches are verified using theoretical analysis and computer simulations.