Perimeter walks of geographic routing in data-centric sensor networks

Abstract

In Data-Centric Storage sensor networks where numerous sensors collaborate to monitor and to report occurrences of environmental events, geographic routing algorithm can be used to route packets efficiently for data insertions and queries. However, the routing algorithm usually routes packets completely around perimeters enclosing destination locations. Such perimeter walks incur considerable amount of redundant traffic on sensor networks and waste node energy. In this dissertation, we analytically show that the overhead generated by perimeter walks is significant in many sensor networks with the number of sensor nodes ranging from hundreds to thousands. Motivated by the result, we propose a basic algorithm for pruning those walks to improve performance of DCS sensor networks that use geographic routing. Under assumptions that localization service is precise and radio coverage is a perfect circle, our proposal incurs no additional communication overhead; only require the knowledge of radio transmission range; but can reduce significant amount of insertion/query overhead. Considering practical scenarios where localization service can be erroneous and node radio range can be irregular, we provide additional parameters that capture effects of location errors and radio irregularity. With the parameters, we mathematically analyze effects of location error and radio irregularity by reasoning on pruning probability of perimeter walks. Our analysis shows two important and interesting facts. Firstly, increasing radio irregularity is similar to reducing node density. When radio irregularity exists, once can increase density of nodes to compensate negative effects of irregular node radios. Secondly, location error is more severe to performance of DCS sensor networks. Particularity, in the presence of erroneous localization, increasing node density does not always improve performance. If sensor networks are sufficiently dense, increasing node density even reduces prunin...