Efficient topology discovery and routing in thick wireless Linear Sensor Networks

Wireless devices such as sensors have increasingly more processing, storage, and networking capabilities, making wireless sensor networks (WSNs) get lots of attentions in recent years. In addition, the cost of sensors is constantly decreasing making it possible to use large quantities of these sensors in a wide variety of important applications in environmental, military, commercial, health care, and other fields. In order to monitor certain types of infrastructures, many of these applications involve lining up the sensors in a linear form, making a special class of these networks which are defined as Linear Sensor Networks (LSNs). In this paper, we take advantage of the linearity of the network to design two graph-search-based topology discovery algorithms for LSNs, namely, LNBN and L2BN. LNBN focuses on minimizing the number of messages used to construct the backbone, while L2BN targets to minimizing the average number of communication hops. The proposed algorithms have several good properties. First, they allow for significant improvement in the scalability of the communication process. Second, the linearity of the structure and the discovered backbone can enhance the routing reliability by jumping over failed nodes by increasing the range. Lastly, they do not require sensor nodes to have location detection capabilities such as GPS, which would otherwise lead to higher costs of sensor nodes.