This Is AuburnElectronic Theses and Dissertations

Node Placement, Routing and Localization Algorithms for Heterogeneous Wireless Sensor Networks

Date

2008-05-15

Author

Dong, Shaoqiang

Type of Degree

Thesis

Department

Electrical and Computer Engineering

Abstract

Wireless sensor network is a very promising technology for many military and civilian applications. The network usually consists large number of nodes and many existing network techonlogies can not be used directly in such networks. To deal with such problems, heterogeneous and hierarchical network architecture have been proposed in recent years. This thesis studies node placement, routing and localization problems in such network architecture. For node placement, we consider a two-tiered wireless sensor network where Lite Nodes (LN, sensor nodes) are placed randomly to sense the environment and Sophisticated Nodes (SN) are placed to aggregate data from LNs and send them to the sink. We intend to minimize the number of SNs and make the SNs form a connected network. We formulate this as an optimization problem and solve it with integer linear programming. Routing algorithm for sensor networks must be scalable and energy-efficient due to large-scale and resource-constraint characteristics of sensor networks. We proposes a reinforcement learning based geographic routing algorithm. The algorithm addresses several issues in traditional geographic routing and considers energy-efficiency. Simulations demonstrate that the routing algorithm can significantly improve the network lifetime. For node localization, we propose a hierarchical localization method for sensor node localization. In addition to LNs and SNs, a small number of anchor nodes with known locations are placed in the network. By using a hierarchical network architecture and UWB technology, only a small number of anchor nodes is needed. Our localization method works in two steps. First, SNs estimate their locations by using the built-in high-precision distance measurement capabilities and locations of anchor nodes. Next, lite nodes use SNs as references to estimate their locations. If a lite node has fewer than three neighboring SNs, it uses SNs and other localized lite sensor nodes as references. Both iterative and non-iterative methods are studied. Extensive MATLAB simulations are performed to study the resulting error performance. It is observed that iterative method produces far lower localization error. The effects of UWB node placement and other parameters such as measurement noise, number of anchor nodes, and communication ranges on the resulting localization error are also presented.