QoS topology control, and energy efficient operations in sensor and ad hoc wireless networks

在無綫傳感器網絡及 ad hoc 網絡中 QoS 拓撲制, 高效能運作等問題

Student thesis: Doctoral Thesis

View graph of relations


  • Hai LIU

Related Research Unit(s)


Awarding Institution
Award date3 Oct 2006


Ad hoc wireless networks and sensor networks have received significant attention in recent years due to their potential applications in battlefield, disaster relief operations, traffic surveillance, environment monitoring and so on. QoS topology control, energy efficient operations are fundamental and important issues in ad hoc wireless networks and sensor networks. This thesis investigates these issues and presents their solutions. The major work of the thesis can be summarized below. First, we studied the energy efficient QoS topology control problem in ad hoc wireless networks. Two cases of the problem were considered: 1) the traffic demands are not splittable, and 2) the traffic demands are splittable. They were formulated as an integer linear programming problem and a mixed integer linear programming problem, respectively. A greedy algorithm and an approximation algorithm with ratio n were further proposed to solve the problem, where n is the number of nodes. Extensive simulations were conducted to evaluate the performance of proposed algorithms. Second, we proposed an efficient algorithm with O(|P|2k) complexity for timeslot assignment problem in TDMA/CDMA ad hoc wireless networks, where P is a path and k is the number of slots in a TDMA frame. The algorithm was further integrated into a QoS call admission scheme for QoS call requests. We proved that a timeslot assignment providing 1 unit of bandwidth on P can be found in O(|P|) time if such an assignment exists. The results had been extended to the case that P can provide 2 units of bandwidth and the general case. Extensive simulations were conducted and the results had demonstrated the superior performance of our method. Third, we studied the relay node placement problem in the two-tiered wireless sensor networks. Given a set of sensor nodes in Euclidean plane, our objective is to place the minimum number of relay nodes to forward data packets from sensor nodes to the sink, such that: 1) the network is connected, 2) the network is 2-connected. For case one, we proposed a (6+ε )-approximation algorithm for anyε >0 with polynomial running time whenε is fixed. For case two, we proposed two approximation algorithms with (24+ε ) and (6/T+12+ε ), respectively, where T is the ratio of the number of relay nodes placed in case one to the number of sensors. We further extended the results to the cases where communication radiuses of sensor nodes and relay nodes are different. Fourth, we studied the maximal lifetime scheduling problem for sensor surveillance systems with k sensors to 1 target. We proposed an optimal solution to find the target watching schedule for sensors, where the lifetime is the duration up to the time when there exists one target that cannot be watched by k sensors or data can not be forwarded to the base station due to the depletion of energy of the sensor nodes. Our solution consists of three steps: 1) computing the maximal lifetime of the surveillance system and a workload matrix by using linear programming techniques; 2) decomposing the workload matrix into a sequence of schedule matrices that can achieve the maximal lifetime; 3) determining the sensor surveillance trees based on the above obtained schedule matrices, which specify the active sensors and the routes to pass sensed data to the base station. This is the first time in the literature that this scheduling problem of sensor surveillance systems has been formulated and the optimal solution has been found. We illustrated our optimal method by a numeric example and experiments in the end. Fifth, we studied the sufficient and necessary condition of 100% deliverability for flooding schemes that are based on only 1-hop neighbors information. We further proposed an efficient flooding algorithm that achieves the local optimality in two senses: 1) the number of forwarding nodes in each step is the minimal; 2) the time complexity for computing forwarding nodes is the lowest, which is O(nlogn), where n is the number of neighbors of a node. Extensive simulations had been conducted and simulation results had shown that performance of our algorithm is significantly better than the existing message efficient flooding methods. Finally, we studied the collision-free delay efficient data gathering problem in wireless sensor networks. We focused on networks where nodes are equipped with two channels. Optimal solutions were proposed for spider networks and tree networks. We further proposed two approximation algorithms with performance ration of 2 for general cases.

    Research areas

  • Wireless communication systems, Sensor networks