无线传感器网络中保证交付的贪婪路由算法

Greedy Routing with Guaranteed Delivery in Wireless Sensor Networks

针对传感器网络提出了一种高效的点对点的路由方法。通过对每个节点分配坐标,将网络映射到由它的若干生成树构成的度量空间,根据节点坐标使用贪婪算法路由,即总是选择离目的节点最近的邻居转发包。该方法在每个节点的路由表中只需要维护邻居的坐标,包首部开销最多为O(log2n)2比特。与很多基于位置的贪婪路由算法相比较,该方法的特点是贪婪路由算法能够保证网络中任意一对节点之间都是可达的,并且路径长度不超过这对节点在生成树上的距离。仿真表明该方法同时能够在路径拉伸度和负载平衡上取得较好的性能。

This paper presents a scalable point-to-point routing scheme for wireless sensor networks. The scheme assigns a coordinate to each node of the network so that the nodes are embedded into a metric space induced by a small size of spanning trees of the network graph, and thus according to the coordinate space a greedy routing algorithm can be used for every pair of nodes, i. e. , nodes always forward packets to the neighbor which is closest to the destination. In the scheme, each node only needs to maintain the coordinates of its neighbors in its routing table,and the overhead of each packet heads is bounded by O （log2n）^2 bits. Compared with many position-based greedy routing algorithms, the scheme ensures that greedy routing is always successful in finding a route to the destination,if such a route exists,and the route is not longer than the routes to the destination in the spanning trees. Simulations show the routing scheme can achieve remarkable performance in both path stretch and node load.