Topology control in large-scale wireless sensor networks: Between information source and sink

With non-uniform traffic patterns in wireless sensor networks due to the many-to-one nature of communications, the traditional definition of connectivity in graph theory does not seem to be sufficient to satisfy the requirements of sensor networks. In this work, a new notion of connectivity (called path-implementability) is defined which represents the ability of sensor nodes to relay traffic along a given direction field (referred to as information flow vector field) D→. The magnitude of information flow is proportional to the traffic flux (per unit length) passing through any point in the network, and its direction is toward the flow of traffic. The flow field may be obtained from engineering knowledge or as a solution to an optimization problem. In either case, information flow flux lines are abstract paths that are assumed to represent desired paths for flow of traffic. In a sensor network with a given flow field D→(x,y), we show that a density of n(x,y)=O(|D→(x,y)|2) sensor nodes is not sufficient to implement the flow field. On the other hand, by increasing the density of wireless nodes to n(x,y)=O(|D→(x,y)|2log|D→(x,y)|), the flow field becomes path-implementable. Path-implementability requires more nodes than simple connectivity. However, it guarantees existence of enough paths connecting the information source to the sink so that all the traffic can be transmitted to the sink. We also propose a joint MAC and routing protocol to forward traffic along the flow field; the proposed tier-based scheme can be further exploited to build lightweight protocol stacks which meet the specific requirements of dense sensor networks.