基于邻近图拓扑构造算法的仿真设计

陈功平 王 红

（六安职业技术学院信息与电子工程学院 安徽六安 237000）

无线传感器网络（wireless sensor network，WSN）由大量微型传感器节点组成，这类节点的主要工作是通过无线电传输模式构建多跳自组网络，从而达到扩大监测区域的目的。在监测区域内的工作包括其协作地感知、采集和处理网络覆盖区域中感知对象的信息，并发送给观察者。网络拓补控制与无线传感网络相结合可以在保障网络连通度和覆盖率的基础上，进一步形成更加密闭的网络环境，可以通过合理利用网络拓补结控制构，减少节点能耗和网络能耗，延长网络生存时间。由此可以看出拓扑控制在无线传感器网络研究中的占有极其重要的地位，将其与无线网络结合，对于无线传感器网络研究来说意义重大。林亭君等人（2018）提出利用风光拓补算法可以提高变电站的运输效率以及提高光伏输出功率的稳定性[1]。谢宜婷等人（2017）提出为了提高图像匹配度，可以利用特征描述算法检测匹配关系，提高运算性能[2]。邹蕾等人（2017）提出通过对空间的层次划分来构建近邻图，能够进一步提高算法准确度[3]。基于此，可以看出，建立一种高效的拓扑控制能够大幅节约节点能耗，能够延长整个网络的生命周期，提高网络连通的稳定性，还能降低相互间信号的干扰，提高MAC协议和路由协议的效率。

一、基于邻近图的拓扑控制建模研究

（一）临近图。临近图分为相对临近图（RNG）以及伽布里图（GG）两种类型。相对临近图(Relative Neighborhood Graph)的定义十分简单：对∀u，v∈V，如果(u,v)∈RNG，则不存在点w，使得max{d(u,w),d(v,w)}＜d(u,v)。该定义等价于图2-1所示以u，v 为圆心的圆的相交区域内不含有其他点。RNG唯一可平面。如果按照定义构造RNG，需要O(N3)时间复杂度。如图1、2所示：

图1 RNG中的边

图2 GG中的边

伽布里图(Gabriel Gravh)属于几何邻近图。含义为：∀u，v∈V，如果边(u,v)∈GG，则不存在点w，使得d2(u,w)+d2(v,w)≤d2(u,v)。该定义等价于图2-2中以u，v为直径的圆中不含第三点w。GG唯一并且可平面。根据定义构造算法时间复杂度为O(N3)[4]。

（二）DRNG和DLSS算法。DRNG和DLSS算法主要由信息收集、拓扑构建以及双向连接的拓扑构建三个步骤组成[20]。两者第一、三阶段类似，主要区别在第二阶段。

为了使算法更加便于理解，首先作如下定义：

1.(u,v)表示从点u至点v的有向边，与(v,u)方向相反；

2.d(u,v)表示点u和点v之间的距离。ru表是节点u的通信半径。可达邻居集合Nu表示节点以最大功率发射所能到达的节点集合。

DRNG算法是基于RNG邻近图的拓扑控制算法。算法流程如图3所示：

图3 DRNG算法流程图

在上面的阶段完成之后将发射功率调整为与最远邻居节点通信所需要的功率。在无线网络中，两个节点必须是双向连通的才能够在拓扑图中形成边。因此还需要将拓扑图进一步的修改，删去只能单边通信的边。与DRNG 算法类似，首先每个节点以自己的最大发射功率周期性的广播Hello消息，通过接收到其他节点的Hello消息确定自己的可达邻居节点集合N。在得到邻居节点集合N之后，DLSS算法通过以下标准确定邻居节点：假设己知节点u以及它的可达邻居子图Gu，当节点v在节点u的直接局部生成图Su上，其中Su是DLSS(u)的输出，并且与节点u只相隔一跳距离时，节点v是节点u的邻居节点，记为DLSS(u-＞v)[5]。

（三）OMNET++模型架构。OMNET++是一款基于组建的模块化的开放网络仿真平台。所以用户可以通过OMNET++简便的描述实际系统结构。OMNET++的模块以分层次的嵌入式模块为主。模块结构在程序中使用NED语言描述。这些模块可以相互间传递消息，也可以多个简单模块（simple modules）组成一个复合模块（compound modules），如图4所示：

图4 简单模块和复合模块

当然为了使这些混合模块能够与简单模块一样使用，在这些混合模块的定义中必须要设定它的“门”，也就是与其他模块相连接的接口。每个模块都是通过输出门发送消息，通过输入门接收消息。而门到门的对应关系就构成了链接，如图5所示。

图5 模块之间的接口与门

二、基于邻近图的仿真实现

（一）通信协议架构。在本文所建立的网络模型中，使用的是CSMA MAC 协议，每个节点在发送数据帧之前，首先要进行载波监听，只有介质空闲时，才允许发送帧。然后随机延时一段时间后，再重新争用介质，重发送帧[6]。

在节点收到信号的时候一层层上传，最后在appl层通过handleLowerMsg(cMessage*msg)判断消息的类型，如果是广播信息，则发送一个reply信息，如果是一个对应自己发送的广播信息的reply 则输出“Received reply from host……”然后删除该消息，否则报错。协议层次图如下图6所示：

图6 协议层次图

（二）功率与通信距离仿真分析。为了观察节点距离与发射功率的关系，实验分别按照功率调整和距离调节，通过多次实验之后得出如下表1与图7所示：

表1 间距与发射功率的关系

图7 间距与发射功率的关系

由图7 可知，两点间间距与发射功率呈正相关，在两点间距离达到60时，发射功率迅速上升。

（三）邻近图算法控制与网络生命周期分析。实验中，设置10个节点随机分布在200m*200m 的范围内，节点的最大发射功率为100mw，节点的最大发射距离为99m，网络允许的最大发射功率为100mw。按照DRNG算法，经计算得到节点对应的发射功率如表2所示：

表2 DRNG算法功率表

按照DLSS算法，经计算得到节点对应的发射功率如表3所示：

表3 DLSS算法功率表

由表2与3比较可得，0号节点在DLSS算法中发射功率较小。DRNG算法和DLSS算法的执行结果表明，网络的拓扑结构相对于原始拓扑图有了明显的简化，简化的通信链路将使网络能耗大大节省，网络的生存时间自然而然的得到延长。

相比而言，DLSS算法要比DRNG算法复杂得多。同时由于DLSS算法是在LMST的基础上产生的，通过拓扑结构图也可以看出通过DLSS算法得到的网络结构图的鲁棒性明显弱于DRNG图。所以DLSS算法在节能的方面确实占有一定的优势，但是在实际应用中，DRNG算法显然更加具有实用性。

三、结论

本文分析了已有的经典DRNG 和DLSS 拓扑控制算法，并且进一步的提出了改进，并且对算法进行了仿真。通过仿真之后以直观的结果显示了拓扑控制算法对网络结构的优化作用，明显地节约了网络的节点能量，延长了网络的生存周期。无线传感器网络是一门面向应用的学科，也只有在实际应用进行研究，它才能得到发展。拓扑控制技术的研究是整个无线传感网络研究中第一个十分重要的方面。它影响着整个网络的性能，效率，生存时间。针对拓扑控制技术研究可以从以综合应用功率控制、层次性拓扑控制和启发机制这个方面进行。综合考虑无线传感网路的鲁棒性、能耗、高效路由协议和MAC协议，在他们之间找到一个平衡点。