基于Agent技术的无线传感网络拓扑分簇算法仿真研究

刘　佳，黄友锐，唐超礼，曲立国，韩　涛

(安徽理工大学电气与信息工程学院，安徽淮南　232001)

0　引言

无线传感器网络(WSN)中的传感器节点通常处在不易接近的恶劣环境中，并采用能量有限的电池供电[1]，由于电池不能随时更换[2]，所以设计能量消耗低，能量消耗均匀，网络生命周期长的网络拓扑结构至关重要[3]。

LEACH算法[4-5]是最早提出的一种自适应分簇拓扑算法，其簇头节点能量消耗较大，且未考虑节点的剩余能量；HEED[6-7]作为一种完全分布式成簇算法，已将剩余能量作为参量引入其中，但对影响簇头选举的因素考虑不全，致使簇头节点的选举不合理。基于多权值优化的分簇算法[8](MWBC)选取多个网络参数作为簇头选举的依据，但其未考虑簇头节点到汇聚节点的距离，对簇头节点的能量消耗影响较大。

文中提出的基于Agent技术的无线传感网络拓扑分簇算法将Agent应用到分簇算法中，由于Agent[9]可以过滤掉大量的冗余信息，所以在簇头选举阶段可以有效减少通信量，降低网络的能量消耗，在簇的更新阶段节约了路由空洞和定时分簇造成的不必要的能量消耗。仿真结果表明，该算法可以节约网络流量，延长整个网络的生命周期。

1　相关假设

假设1：每个节点Agent上都有移动Agent的运行环境，且初始能量基本相同。

假设2：无线传感器网络中每个节点Agent都有唯一编号，且已知自己和邻居节点Agent的编号。

假设3：部署的节点Agent分布在一个二维平面内，可用坐标(xv，yv)标识自己的位置。

2　Agent类型定义

将无线传感器网络看作是一个多Agent系统，系统框图如图1所示。

图1　基于Agent的WSN网络框图

图1中系统包括6种类型Agent，类型及功能定义如下：节点Agent：存储与节点相邻的节点信息，并向移动Agent提供外部访问和更新簇信息的接口；簇头Agent：收集簇内节点Agent发送的数据；簇内移动Agent：由簇头Agent产生，用于修复路由空洞和孤立节点问题；簇间移动Agent：由汇聚Agent产生，将用户布置的任务分配给簇头Agent，并将簇头Agent收集到的数据传送给汇聚Agent处理；汇聚Agent：处理簇头Agent收集的信息和向簇头Agent发送用户发布的任务；用户Agent：对传感器网络发布任务，收集汇聚Agent数据等。

3　基于Agent技术的无线传感网络拓扑分簇算法

该算法分为首轮成簇和簇的更新2个阶段。

3．1首轮成簇阶段

簇头Agent由每个节点Agent的剩余能量、发射范围内的邻居数目、与所有邻居的平均距离、与基站的距离4个因素共同决定，通过计算各节点Agent的权值大小，选出最佳簇头Agent节点。

具体操作流程如下：

步骤1：每个节点Agent向其周围节点Agent发送询问报文，收到询问报文的节点Agent回复应答报文，节点Agent每收到一个应答报文，计数器加1，以统计发射范围内的节点Agent数目之和，用Nv表示。

步骤2：节点Agent已知自身的位置信息(xv，yv)，通过接收到应答报文中包含的邻居节点Agent的位置信息(xn，yn)，可计算出节点Agent到其邻居节点Agent的平均距离Dnv。

(1)

步骤3：网络中的节点Agent接收到汇聚节点Agent发送的询问报文后，提取出汇聚节点Agent的位置信息(xb，yb)，通过计算得出自己和汇聚节点Agent的距离Dbv．

(2)

步骤4：各Agent利用已知信息，计算其剩余能量EV．计算公式如下：

(3)

式中：Ev和E0分别为节点Agent的剩余能量和初始能量；T1和T2分别为节点Agent担任簇头Agent和未担任簇头Agent的时间；Nv为节点Agent发射范围内节点的数目之和；countv表示各邻居节点Agent发送给该节点Agent的总数据量；e表示簇头Agent融合单位数据所消耗的能量。

步骤5：完成以上各步骤后，节点Agent利用式(4)计算各自的权值。

(4)

式中：δ为一般情况下簇头Agent能够处理的理想节点数；λ1～λ4为权重因子，理想节点数和权重因子均可根据节点所处的环境变化随时调整，且权重因子之和为1。

步骤6：每个节点Agent计算出自己的权值后向全网广播自己的权值，并将接收到邻居节点Agent报文中的权值与自己的权值比较，若其在邻居节点Agent中具有最小权值，则该节点Agent成为簇头Agent并向周围节点Agent发送通知报文，宣布自己成为簇头Agent。

步骤7：节点Agent根据接收到信号强度的大小，向信号强度最大的簇头Agent发送请求报文，申请加入该簇，经过簇头Agent同意后加入该簇。

步骤8：重复步骤6～步骤7，所有节点Agent都加入到某一特定的簇后，完成分簇过程。

3．2簇的更新阶段

该算法不是周期性地进行簇头选举，而是采用事件通知Agent的启发机制，簇内移动Agent若发现路由空洞问题或孤立节点存在，修复后及时通知簇内节点Agent进行新一轮的簇头选举；或当簇头节点Agent的权值高于簇内其他节点Agent时，也会进行新一轮的簇头选举。

3．2．1路由空洞的修复

对于节点A来讲，到达簇头节点一个正常的路线是AFIO，如图2(a)所示。若节点E和F已经失效，通常节点B被选择作为节点A的下一跳节点，路由是ABCDGHIO，形成了路由空洞问题，如图2(b)所示。

(a)正常路由

(b)路由空洞

图2路由空洞

有时绕过空洞不是最优解，A直接发送到I的能量消耗远小于绕过空洞所消耗的能量。此时，簇内移动Agent可以用来控制节点A的发射功率。当簇内移动Agent从A到达I，发现发送到I的能量消耗远小于绕过空洞所消耗的能量，再回到节点A，通知节点A直接发送至节点I，如图3所示。

图3移动Agent解决路由空洞

移动Agent将会在每个节点上做出一个判断，如果移动Agent发现在节点k处满足式(5)，然后它回到节点i处，让i直接发送到节点k。

ETX(i，k)

(5)

此外，考虑到能源假设的平衡，传输功率应该有一个上限Emax，若一个节点长期使用大功率传输，它将很快耗尽自己的能量。因此，能量假设应该满足式(6)的制约条件。

ETX(i，k)

(6)

3．2．2孤立节点的修复

若一个或一些节点和网络的其他部分失去连接，则称为孤立节点，如图4所示。事实上，孤立节点的数据仍是有价值的，不应该被浪费。

图4　发现孤立节点

图5　孤立节点重新加入

定义一个时间阈值Tmax，如果节点超过Tmax时间没收到簇内移动Agent，它将把本身作为一个孤立节点。然后用最大发射功率周期性进行广播。移动Agent收到这个消息后，通知孤立节点通过相应的传输功率创建新的链接，如图5所示。当节点A重新加入网络，新的路线是BCADE。

4　仿真结果分析

文中采用OMNET++仿真平台[10-11]作为仿真工具，并将新提出的算法和MWBC算法在OMNET++仿真平台上运行，对整个网络的分簇能量消耗、丢包率、生存周期(第一个节点死亡时的分簇轮数)3个方面进行仿真分析和比较，仿真结果如图6、图7、图8所示。

文中算法初始仿真环境主要参数配置情况如下：初始能量E0为12 J，权重因子λ1、λ2、λ3、λ4分别为0．3 J、0．2 J、0．2 J、0．3 J，节点距离临界值d0为150 m，仿真区域面积为100×100 m2，Eelec为50 nJ/bit·m-1，εfx为10 pJ/bit·m-2．

图6　每轮分簇消耗能量对比图

图6所示是每轮分簇能量的消耗，两种算法每轮分簇消耗的能量均随着节点数的增多而增多，因为随着节点数的增多分簇时需要处理的数据量增多，加大了能量消耗，而文中算法明显比MWBC算法[8]节省能量。因为信息传输过程去除了大量冗余信息，减少了通信消耗的能量。此外，在分簇过程中簇内移动Agent及时对路由空洞问题进行修复，节省了由于路由空洞造成的能量浪费。

由图7可知，文中算法丢包率比MWBC算法[8]小，是因为文中算法利用Agent的思想，每个节点Agent都具有分布式数据处理功能，减少了所需传输的数据量，使得数据传输过程中的数据冲突减少，在簇的更新阶段利用移动Agent进行孤立节点的修复，也有利于降低丢包率。

图7　丢包率对比图

由图8可以看出，文中提出的算法比MWBC算法[6]具有更长的网络生存时间，节点数增多时这种优势更加明显。文中算法将簇头Agent到汇聚Agent的距离作为簇头选举的参量之一，可使簇头的选举更合理，能量消耗更加均匀；在簇的更新阶段采用启发机制减少了由于定时分簇造成的能量浪费。此外，利用簇间移动Agent把簇头Agent收集的信息直接传送给汇聚Agent，也可节省簇头Agent的能量，减少簇头节点因处理大量信息而提前死亡的风险。

图8　网络生存时间对比图

5　结束语

文中提出了一种基于Agent技术的无线传感网络拓扑分簇算法，该算法在分簇初期全面考虑影响簇头选举的多种因素，根据不同的应用环境动态调整加权因子；在簇的更新阶段利用移动Agent及时对簇内问题进行发现和修复，修复完成后进行新一轮的簇头选举。仿真结果表明文中提出的算法比HEED算法[6]和MWBC算法[6]更具优势，可以获得更加合理的簇分布，节省能量，延长整个网络的生命周期。适合在大规模部署或处在恶劣环境中的网络中推广。参考文献：

[1]周治平，王亭．一种节能的无线传感器网络分簇算法．计算机工程，2011，37(22)：85-87．

[2]孙利民，李建中，陈渝．无线传感器网络．北京：清华大学出版社，2005：95-98．

[3]刘新华，李方敏．一种基于负载均衡的无线传感器网络分布式定向分簇算法．计算机研究与发展，2009，46(12)：2044-2052．

[4]潘霞，于宏毅．一种基于LEACH的能耗均衡分群算法．电路与系统学报，2012，17(1)：75-80．

[5]吕涛，朱清新等．一种能耗均衡的无线传感器网络分簇算法．计算机应用，2012，32(11)：3107-3111．

[6]黄河清，姚道远．一种基于多权值优化的无线传感器网分簇算法研究．电子与信息学报，2008，30(6)：1489-1492．

[7]DIMOKAS N，KATSAROS D，MANOLOPOULOS Y．Energy-efficient distributed clustering in wireless sensor networks．Journal of Parallel and Distributed Computing，2010，70(4)：371-383．

[8]刘安丰，任炬．基于Omnet++的WSN路由实验教学平台．计算机工程，2012，38(11)：258-261．

[9]曹永洁，齐建东．无线传感器网络能耗均衡的流量调节机制．计算机工程，2012，32(11)：99-101．

[10]杨光旭，刘方爱．OMNeT++平台上无线传感器网络仿真系统的研究．计算机应用研究，2011，28(9)：3443-3446．

[11]王燕，张锐．基于三步簇头竞争机制的分簇算法研究．仪表技术与传感器，2013(4)：90-93．