无线自组织传感网邻居节点检测协议及其实现

林 炳，仇 建

(杭州电子科技大学计算机应用技术研究所，浙江杭州310018)

0 引言

定义两个具有有效通信链路的节点互称为邻居，可以用一个固定半径来表示节点有效通信范围，而所有在此范围内的节点都是其邻居，这个模型被称为盘状模型［1］。在分布式传感网初始化之前，节点没有任何邻居信息，无法形成网络。为实现传感网自组织、路由选择、介质访问控制和数据聚合等工作，邻居节点检测必不可少。之前，已经有不少研究人员在这个问题上进行了一定的研究，比如最佳链路状态路由［2］和按需自组织路由［3］等路由协议方案。由于传感网的能量受限，一些减少邻居查找耗费时间以降低能耗的扩展方案也被相继提出。例如，为使邻居检测过程更加适应高移动性网络，邻居信息更新频率可自适应调整［4］，通过链路层反馈的邻居检测方法也是达到快速邻居检测的一种扩展方案［5］。但是，以上方法存在几个比较普遍的问题，包括探测率不足、耗时过久、能耗较高等。为解决以上问题，本文提出了一种改进的邻居检测方案，并建立以接收端为视角的邻居检测分析模型，使其能适用于大部分实际情况，并利用网络仿真和测试床检测对其进行验证。

1 方案描述

本文提出的邻居检测方案采取随机选择时间片的方式广播Hello控制包形成单方向邻居检测，并通过重复广播来提高邻居检测概率。

1.1 网络模型和参数定义

传感网节点由于没有预先分配信道，每个节点通过随机时间接入信道来广播控制数据包以交换名片信息，从而实现邻居检测。为便于方案描述，提出以下假设:

(1)网络同质，单位密度为ρ个节点随机分布在一个二维平面内。节点具有相同传输功率和接受半径，因此每个节点的有效无线电接收范围都等于r;

(2)信道按时间划分成多个时间片，每个时间片的长度等于传输持续时间加上包的最长传输延迟;

(3)所有节点完全同步，数据包传输都发生在一个特定的时间片内;

(4)数据包丢失的唯一原因是碰撞，或称之为两跳邻居同步传输干扰。以接收者的角度来说，两跳干扰等同于两个一跳邻居同时传输，此假设有益于之后分析;

(5)简单来讲，定义一跳邻居和两跳邻居的平均值分别为N1和N2。T个连续时间片组成一个帧。经过n个帧的时间后，检测到N1个一跳节点和N2个两跳节点的概率分别为p1(n)和p2(n)。

1.2 邻居检测过程

作为发送方，每个节点从每帧中随机选择一个时间片，广播包含自身ID和当前单跳邻居ID的信息包。因为无法实现预先规划，碰撞无法避免从而部分包传输失败。随着多次重传，更多的单跳邻居能够成功接收该节点发送的信息。

作为接收方，一旦节点接收到邻居节点发送来的邻居信息包，它将存储传输节点的ID至单跳邻居表中。而邻居信息包中存放的单跳邻居ID被识别为临时两跳邻居，并存储在临时两跳邻居表内。这些临时两跳邻居可能与接收节点直接通信，从而确认为单跳邻居。在整个过程结束后，通过排除单跳邻居ID号，可以记录正确的两跳邻居表。

2 理论分析

作为检测两跳邻居的基本步骤，将逐步分析一跳邻居检测模型，以确定最佳的帧结构。虽然已经对这种情况做出推导［6］，但本文的分析是从接收者的角度出发，如图1所示的节点A，解决该情况提供了更好的方法。

从图1中可以很清楚地发现，节点A能在特定的时间片成功接收的条件是，当且仅当节点B－F中的一个选择了这个特定时间片广播信号包，并且其他任何一跳邻居(N1－1)节点和节点A本身都必须保持沉默。例如，节点C和E选中了第一个帧内的相同时间片，那么节点A将不能收到两者的信号包。每个节点选中某个时间片的概率是1/T，T是一个帧包含的随机进入信道的时间片数量。因此，单个帧时间内任意节点被检测为邻居的概率是。p=(1 －1/T)N1。

在整个网络范围内，这个概率就等于单个帧时间内检测到的一跳邻居数量占总邻居数的平均百分比:

图1 一跳邻居检测插图

推而广之，经过n个帧时间后单跳邻居被发现的概率为:

两跳邻居检测数学模型的建立可以尽量减少邻居检测周期的总持续时间，总持续时间等于帧长度乘以帧数量:

重新整理式3，n可以表达成关于T的等式:

因此，该过程的总持续时间可以描述成一个关于指定概率(检测出所有一跳邻居的概率)的表达式:

式中，一跳邻居检测概率是系统需求，平均邻居数N1由网络拓扑结构决定，q由给定调制方案下的无线电信道特性确定，式5只取决于如何选择帧长度T。

因此，为了获得一个尽量小的f(T)，最常见的操作就是找到一个特定的T使得df(T)/dT=0，求导结果为:

通过检验式5的二阶微分，不难发现发f(T)的最小值点存在且只有一个，但求取数值解的过程过于繁琐而且精确度超过实际应用所需。因此，采用MATLAB仿真计算的方式求取近似曲线。结果如图2所示:

通过检验拟合曲线，可以得到最佳值:

当帧长度是一跳邻居的1.45倍时，特定概率下的一跳邻居检测速度是最快的。如果帧长度T比1.45N1短，就需要更多的帧来达到相同的一跳邻居检测概率。如果帧长度T相比1.45N1长，即使需要的帧更少，但发送邻居信号的总持续时间仍然大于采用1.45N1时的长度。

图2 最佳信号包传输时间帧长度

3 仿真结果与分析

为了验证本文提出的相关理论，采用OMNET仿真和节点实际硬件测试。其中，仿真的场景根据节点数量的不同分为3个:50个节点随机分布在边长为500m的正方形区域中;200个节点随机分布在边长为1 000m的正方形区域中;800个节点随机分布在边长为2 000m的正方形区域中。所有节点都拥有100m有效接收范围，而任意数据包碰撞将导致接收失败。实验结果显示，在第8个时间片时检测到的数量基本达到95%以上。单跳邻居的平均数量为5.3，根据式7预测到的最短持续时间的帧长度是7.75个时间片。由于它并不是一个整数，所以可以将8个时间片作为最佳帧长度。

在测试床硬件实验过程中，如图3所示，实验节点数为25个，采用接近正6边形的分布方式，平均单跳邻居数量为6，根据式7预测到的最短持续时间的帧长度是8.7，取整为9。实验前台显示过程和最终结果如图4所示。图4中界面上方为对应拓扑图，左下方为节点相互之间的连接关系，黄色表示单跳邻居关系而绿色表示两条邻居关系。图4右下方，每个节点的单跳和两条节点数被表示。经过7次重传后，全部的节点连接都被找到。

图3 无线传感网测试环境

图4 硬件实验结果

4 结束语

无线传感网络和自组织网络不管是在处理能力还是能量上均受到限制，使用消息重传机制等方法查找邻居节点由于能耗高，耗时久并不能满足需求。本文提出的邻居检测方案，以接收端为视角，采用随机选择时间片的方式发送Hello消息包。本文通过严谨的理论知识分析最佳帧结构，并利用网络仿真和测试床检测验证。在未来，可以将此邻居检测方案加入实际部署的无线传感网络系统，从而进一步体现其广泛适用性。

［1］ Gupta P，Kumar P.The Capacity of Wireless Networks［J］.IEEE Transactions on Information Theory，2000，46(5):388－404.

［2］ Clausen T，Jacquet P，Laouiti A.Optimized Link State Routing Protocol［C］.Lahore:IEEE International Multitopic Conference，2001:233 －246.

［3］ Perkins C，Belding-Royer E，Das S.Ad Hoc On-demand Distance Vector Routing［C］.Vienna:Internet Engineering Task Force，2003:152 －168.

［4］ Benzaid M，Minet P，Agha K.Integrating Fast Mobility in the OLSR Routing Protocol［C］.New York:IEEE Conference in Mobile and Wireless Communications Networks，2002:310 －356.

［5］ Voorhaen M，Blondia C.Analyzing the Impact of Neighbor Sensing on the Performance of the OLSR Protocol［C］.San Francisco:International Symposium on Modeling and Optimization in Mobile，2006:248 －276.

［6］ Bao L，Aceves J.Hybrid Channel Access Scheduling in Ad Hoc Networks［C］.California:IEEE International Conference on Network Protocols，2002:451 － 485.