无线传感器网络中一种基于标号的贪婪转发算法*

侯贵升，吴晓蓓，黄 成，徐志良

（南京理工大学自动化学院，江苏南京 210094）

0 引言

在无线传感器网络（wireless sensor networks，WSNs）中［1］，因应用的需求，通过定位算法［2，3］节点能在大多数情况下较容易地获得自身的物理位置。因此，基于地理位置的路由算法在WSNs中得到了广泛的研究。地理路由普遍使用贪婪转发策略传输数据，即在邻居中选择距离目的节点最近的节点作为下一跳节点。

在实际网络中，由于节点部署不均匀，节点间存在障碍物或部分节点失效等原因，贪婪转发往往会遭遇“路由空洞”，即在邻居中找不到比自己更接近目的节点的下一跳节点。为解决该问题，人们提出了许多改进算法［4～6］。文献［4］提出的GPSR协议使用基于右手法则的边缘转发模式处理路由空洞问题，协议简单，但对空洞不具有感知性，因而，选路盲目。对此，文献［5］提出了改进，让节点掌握两跳邻居信息，提前感知空洞的存在，从而尽可能及时绕开，但显著增加了节点存储开销。文献［6］在网络拓扑局部平面化的基础上，通过探测包建立的路标，使后续数据包避开空洞，但大量探测包的发送增加了节点通信开销。同时，这些协议均依赖于平面化算法，而该算法对节点位置和通信半径误差敏感:随着误差增大，算法会逐渐失效，进而导致路由环路。另外，平面化算法对节点的运算和存储能力要求较高。

为此，本文提出了一种基于节点标号的贪婪转发（label-based greedy forwarding，LBGF）算法，其核心思想是:将网络中的节点组成一个以位于网络中……