| Recent dramatic development in micro-electronic-mechanical systems (MEMS), wireless communications and digital electronics have lead researchers and industry manufacturers to develop small size, low-power, low-cost sensor devices. Such devices can integrate data processing, communications and sensing capabilities. A wireless sensor network (WSN) of the type investigated here refers to a group of sensors, or nodes, linked by a wireless medium to perform distributed sensing tasks. Connections between nodes may be formed using infrared devices or radio frequencies. Wireless sensor networks will be used for such tasks as surveillance, widespread environmental sampling, security, and health monitoring. Much of the research in sensor networks is funded for military tasks, but applications such as forest fire detection and rush-hour traffic monitoring exemplify the versatility envisioned for this rapidly expanding technology. Many successful sensor applications have been deployed in very specialized networks, such as UCBerkeley's Smart Dust [1], MIT's mu-Adaptive Multidomain Power aware Sensors [2], and UCLA's Wireless Integrated Sensor Networks [3]. Wireless Sensor Networks can contain hundreds or thousands of sensor nodes. Due to wireless sensor network's properties of low-energy-efficiency, large-scale, low cost and lossy nature, the development of efficient routing protocols for these large and dense wireless sensor networks is an interesting research topic.;This research focuses on the design and implementation of protocols for dense and wireless sensor networks. More specifically, we propose to combine an underlying topology with XMesh, the commercial multihop routing protocol developed by Crossbow Technology Inc. [4] for their wireless sensor nodes. Crossbow Technology Inc. has been one of the major vendors for wireless sensor networks. Its powerful battery-powered platform runs on the open-source TinyOS operating system. With this operating system, developers can control low-level event and maintain task management. Its multihop routing protocol called XMesh is a distributed routing process. Routing decisions are based on a minimum transmission cost function that considers link quality of nodes within a communication range. However, there are no limits on the path length. In extreme cases and for large networks, it is conceivable that a packet may need to hop through many intermediate nodes before reaching its intended destination.;In an effort to limit the path lengths, we propose to impose an underlying connectivity graph for XMesh [5] [6]. The underlying connectivity graph is a virtual topology of the network, hence the name "Topology-Based Routing". Instead of being forwarded to the best link quality node among all neighbors within communication range, a packet is being routed according to the shortest path routing of the underlying graph. In the event that multiple shortest paths exist, the one with the best link quality is chosen. The purpose of the underlying connectivity graph is to impose a virtual topology that facilitates routing and guarantees a bounded path length. An ideal underlying graph should guarantee a small number of hops between nodes and should possess a simple routing algorithm.;Cayley graphs from the Borel subgroup have been known as the densest degree-4 graphs and all Cayley graphs are vertex-transitive or symmetric [7, 8]. In this work, we propose a topology-based routing for Xmesh with Cayley graphs as the underlying virtual topology. To evaluate the performance of the proposed protocols, both computer simulation via Power TOSSIM [9], an emulator for wireless sensor network, and experimental verification are included. We show that, indeed, by imposing a Cayley graph as an underlying graph, the average path lengths between nodes is smaller and that the averaged power consumed is less than the original Xmesh. Furthermore, an adaptive version of our proposed protocol also ensures more even power consumptions among nodes in the network, which will help prolong network lifetime. |
