An Improved Greedy Geographic Routing in Large-Scale Sensor Networks for reduction of local minima problem

Abstract: Geographic (or geometric) routing is known for routing messages in greedy manner. It means that the current node selects a neighbor node that is closest to the destination and forwards the message to it. Despite its simplicity and general efficiency, this strategy alone does not guarantee delivery of message due to the existence of local minima (or dead ends). If we want to overcome local minima then it is necessary for nodes to maintain extra nonlocal state or to use auxiliary mechanisms. we study, how to facilitate greedy forwarding by using a minimum amount of such nonlocal states in topologically complex networks. Specifically, we investigate the problem of decomposing a given network into a minimum number of greedily routable components (GRCs), where greedy routing is guaranteed to work. We consider an approximate version of the problem in a continuous domain, with a central concept called the greedily routable region (GRR). We study about GRR concerning its geometric properties and routing capability. We then develop simple approximate algorithms for the problem. Greedy approach presented in this paper performs well in terms of data integrity parameter i.e. number of packets lost is minimized and also time required for transfer of packets from source to destination is minimized in our greedy approach.

Keywords: Wireless sensor networks, geographic routing, Decomposition, local minima