Practical Connectivity-based Routing in Wireless Sensor Networks using Dimension Reduction

Connectivity-based routing protocols provide an attractive option for point to point communication in wireless networks due to its potential for low routing overhead. However, when the entire hop-count vector is used to address each node, the communication and storage overhead in the packets are often so high that it is not feasible to implement existing connectivity- based routing protocols infeasible on resource-constrained sensor networks. In this paper, we apply the technique of dimension reduction, in particular principle component analysis (PCA), to the hop-count vectors. Compared to the original hop-count vector, the embedding coordinates preserve the network geometry with much lower overhead, making their use much more practical on current sensor platform. Simulation results show that the coordinates computed by PCA can achieve higher packet delivery ratio, lower path stretch and shorter flooding range in local minimum cases. We have also implemented the PCA algorithm on MICAz motes and conducted experiments in a testbed containing 48 nodes deployed on two floors of an office building. With the use of 9 landmark nodes and only 3 dominant components, the PCA coordinates can achieve 95% of the delivery ratio obtained using full hop-count vector and maintain an low path stretch of 1.12.