Battery-aware and energy-efficient algorithms for wireless networks

This thesis proposes an integrated suite of battery-aware and energy-efficient algorithms for routing and scheduling in wireless mobile ad hoc networks, wireless sensor networks and wireless mesh networks. The thesis includes several closely related topics in wireless networks: (1) On-line computable mathematical battery models for efficient battery capacity calculation on wireless devices; (2) Battery-aware routing schemes for wireless mobile ad hoc networks; (3) A battery-aware backbone scheduling algorithm for self-organized wireless sensor networks; (4) A cross-layer scheduling scheme for urban area high density sensor networks; (5) Battery-aware hot spot covering algorithms for wireless mesh networks; (6) Battery-aware transmission radius scheduling algorithms for wireless mesh networks; (7) Battery-aware client driven mesh router scheduling algorithms for wireless mesh networks. Wireless networks, such as wireless mobile ad hoc networks, wireless sensor networks and wireless mesh networks, have played an increasingly important role in a wide range of applications. Different wireless networks are composed of different wireless devices with various network architectures. The wireless mobile ad hoc network consists of various mobile and battery-powered wireless devices, such as PDAs, laptops and cellular phones. These wireless personal devices form the network in an ad hoc way to let devices communicate with each other. The wireless sensor network is composed of hundreds or thousands of distributed wireless sensors, with each sensor having limited battery energy supply, transmission radius and sensing capability. Sensed data are continuously propagated to a data sink. The wireless mesh network consists of a mix of fixed routers and mobile clients interconnected via access points. Wireless mesh network provides Internet connections to its mobile clients. More and more mesh network applications require mesh routers to be battery-powered due to their flexibility to deploy and their independency of wall power. Battery power has emerged as a key component for energy management in these wireless networks, especially for packet routing and wireless device scheduling. With battery technology lagging behind, the batteries on wireless personal devices, wireless sensors and mesh routers can only last a few hours for work. Although the energy capacity of batteries has been increased by 10% to 15% per year, it still cannot keep up with the increasing energy demand of wireless devices. It is critical to improve energy efficiency of these wireless networks. This thesis provides a suite of battery-aware and energy-efficient algorithms and schemes for routing and scheduling in wireless mobile ad hoc networks, wireless sensor networks and wireless mesh networks. (1) The on-line computable, discrete time mathematical battery models are designed to accurately calculate battery discharging loss and battery residual capacity in an energy-efficient way. The calculation of battery discharging loss in the models is simplified and requires low computation complexity and little memory. (2) A battery-aware power metric is introduced for battery-aware routing in wireless mobile ad hoc networks. Based on the metric, battery-aware routing scheme and prioritized battery-aware routing scheme are proposed to improve energy efficiency of packet routing in wireless mobile ad hoc networks. (3) A virtual backbone scheduling scheme for data propagation and distribution among sensors is proposed based on the mathematical battery model. The scheme constructs a battery-aware connected dominating set to let fatigue sensors recover batteries and prolong the lifetime of wireless sensor networks. (4) A crosslayer scheduling scheme is proposed for urban area high density wireless sensor networks. The scheme consists of three parts: the spanning tree partition algorithm to control the topology, the intersection MAC layer protocol to provide efficient MAC communication around urban intersections and the urban emergency service algorithm for differentiated network services. (5) A router-level battery lifetime optimization scheduling algorithm is proposed to maximize the lifetime of battery-powered mesh routers. A network-wide spanning tree scheduling algorithm is designed to improve lifetime of wireless mesh networks with battery-awareness. (6) A battery-aware mesh network energy scheduling scheme is proposed to dynamically schedule multiple input multiple output mesh routers’ radii based on battery behaviors. The scheme consists of two algorithms: the coverage algorithm and the backhaul routing algorithm. Both algorithm adopt the battery model designed for multiple input multiple output mesh routers. (7) A cross-layer battery-aware client driven scheme is designed to efficiently schedule mesh network coverage. The key idea of this scheme is to let neighboring mesh routers collaboratively adjust their transceiver radii based on positions of mesh clients. This scheme also propose the MAC layer algorithm to jointly minimize the cost among different layers.