面向MANET簇内和簇间路由的增强分布式加权聚类算法

摘要

特别是部署在恶劣环境中的manet，黑客会试图扰乱安全的数据传输并耗尽宝贵的网络资源。由于MANET是电池供电的网络，保留网络资源是必须的。为了资源受限的计算、高效的路由和增加网络的稳定性，网络被划分为更小的组，称为集群。集群结构由簇头(Cluster Head, CH)、普通节点和网关组成。CH选举是一个突出的研究领域，使用许多指标开发了更多的算法。为了提名有效的CH，提出了一种增强型分布式加权聚类算法(EDWCA)。具有较长生命周期的CH维持网络生命周期，为此，还选出了二级簇头(SCH)。该方法考虑了CH选举节点的距离、电池电量、度差和速度等指标。利用NS-2网络模拟器对该算法进行了性能评估，并与现有的分布式加权聚类算法进行了比较。

关键字

MANET, EDWCA，聚类，簇头，次级簇头

介绍

MANET是一种自我导向的、短命的移动节点联合，它们通过无线信道和中间节点相互通信。它不需要任何固定的基础设施，也不需要集中管理。将这些移动节点联网预计将对许多军事、应急、商业、教育、娱乐和民用应用的效率产生重大影响。由于节点受能量约束，链路受带宽约束，且拓扑结构变化不可预测，因此MANET中的路由是一项繁琐的工作。

路由有两种实现方式，一种是平面结构，另一种是分层结构。扁平结构路由更适合于网络规模较小、稳定的情况，所有节点的作用和责任相同。分层结构路由很适合于MANET这样的大型动态网络，节点被分配不同的角色，承担不同的责任。

聚类是将网络以分层方式划分为更小的组(地理上接近的节点)的过程，称为集群。这种类型的路由减少了节点之间交换的控制流量。每个集群由三种不同类型的节点组成，它们是一个簇头节点，一个或两个网关节点和许多普通节点。CH管理与其集群成员关联的所有活动。网关是在集群之间交换信息的中间节点。普通节点是用于数据采集的简单节点。

最近研究者们提出了许多聚类算法，我们的算法是分布式加权聚类算法的增强版。如果整个电池在CH中耗尽，这将导致CH的寿命下降，并且特定的集群变得孤立。[1]这种关键情况由我们提出的增强分布式加权聚类算法(EDWCA)通过具有次级簇头(SCH)和网关节点来处理。SCH将扮演CH的角色，并管理集群活动。

在我们的工作中，簇头的选择是基于移动节点的距离、电池电量、度差和速度等指标。移动节点的聚类结构如图1所示。

本文的其余部分组织如下。第二节介绍了集群形成和集群长选举机制的相关工作。第3节介绍了建议的集群内和集群间数据传输体系结构和路由方案。第4节介绍绩效评估，最后，第5节介绍结论和未来工作。

2文献综述:加权聚类算法

Naveen Chauhan等人，[2]提出了一种基于分布式加权集群的manet路由协议，在该CH中，基于组合权重指标选择了多个系统参数，如节点度、传输范围、能量和移动性。CH负责集群之间的路由。在该算法中，如果CH突然死亡，则没有其他处理方法。

Wojciech Bednarczyk,Piotr Gajewskil[3]提出了一种基于加权参数的改进MANET聚类算法，在这种方法中CH选择考虑节点度、接收功率水平、静止因子和剩余电池水平。该算法通过改变权重因子适用于不同的场景。

•Sahar Adabi等人，[4]提出了“一种新型的移动自组织网络分布式聚类算法”，其中(DSBCA)每个节点通过线性算法计算其分数，基于电池剩余量、邻居数量、成员数量和稳定性。该节点的邻居被告知该分数值。比较得分，选出得分最高的节点为CH。

•Rani V. G和Punithavalli M.[5]提出了MPBCA:基于机动预测的MANET聚类算法，在该方法中，基于距离、机动、剩余电池电量和传输距离，将最小权重的节点选为CH。在这个过程中，缓慢移动的节点被识别出来，这些节点将扮演CH的角色。

“Dahene Amne et.al[6]提出了一种用于移动传感器网络的节能安全加权聚类算法，该算法基于行为水平、移动性、节点与邻居的距离、剩余能量和连通性程度五个指标进行CH选择。在这种方法中，行为水平(BL)是用于选举的关键指标。采用异常检测算法计算出的BL，使行为异常的节点远离聚类。

Muthuramalingam。S[7]等人提出了一种基于迁移率预测的manet动态聚类算法，该算法采用传统的WCA算法进行CH的选择，而采用线性自回归方法预测聚类的迁移率。移动的预测是基于它之前访问过的位置。

洪tzung - pei和Cheng-Hsi[8] Wu提出了一种用于确定异构传感器网络应用节点的改进加权聚类算法，本文提出了一种基于加权聚类算法的改进算法(IWCA)。选择CH考虑了5个因素，分别是距离、度差、移动性、累积时间(它作为CH)和节点的新因素特征。权值最小的节点选为CH。

3算法

本文的工作主要包括初始化阶段和数据传输阶段。

A.初始化阶段

1)权重计算:

一开始移动节点被分配了唯一的ID。每个节点将自己的ID值广播给自己的一跳移动节点，形成一个邻居表。每个节点的权重是根据多个指标计算的，如距离、电池电量、节点度数差和节点的移动性或速度。每一簇中每一跳的节点之间的距离。EDWCA根据上述参数执行聚类，并选择集群头进行高效聚类。节点“n”的权重(Wn)由式(1)计算如下

Wn = W1*En+W2*Δn -W3 *Sn + W4*Dn (1)

En -节点n的能量，用焦耳表示

Δ n节点“n”度差

Sn -节点n的速度

Dn -节点n与其邻居的距离

W1 W2 W3 w4是系数

为这些系数赋值为1 0.08,2 0.6,3 0.02,4 0.3 WWWW。考虑移动模式几乎相似的节点，因此速度系数赋值最小。度差和距离被认为是最重要的，因此它们被赋予更高的值。这些系数的和是1。距离、速度、能量、度差之和按DWCA计算。在找到自己的权重后，每个节点根据邻居表将其权重广播给邻居。邻居表中包含一跳可达节点ID及其权重。

2)簇首选举:

在此阶段，每个节点都向在其传输范围内的相邻节点发送Hello消息。Hello消息包括节点ID及其权重值。当一个节点收到预定义数量(Np)的Hello报文时，它会比较收到的所有权重，权重最高的节点将被宣布为Cluster - Head (CH)，然后新选出的CH将广播一个消息“我是Cluster - Head (CH)”。失败的CH可能会导致集群保持隔离状态，直到下一次重新集群。同时，移动节点的重要数据无法上报，可能丢失。为了避免这个问题，还根据下一个最高的权重选出一个次级簇头(SCH)。SCH存储备份路由和集群信息。

3)集群形成:

在集群形成中，集群节点成员在一跳距离内向CH发送自己的加入消息，如“我是集群成员”。CH将维护每个移动节点的成员id和角色(普通节点、SCH、网关节点、邻居CH)的成员列表。假设一个节点从不同CH接收到多条CH消息，那么它将成为Gate Way节点，负责集群间通信。聚类形成和数据传输流程如图2所示。

B.数据传输阶段

此阶段由子模块组成，如集群间通信和集群内通信。在集群内，为了避免簇头的拥塞，采用了时分多址。在集群间通信中，采用AODV协议[12]，以实现按需获取路由和最小化节点内存使用。

1)集群间路由:

CH使用传统的AODV协议，通过网关向相邻集群发送RREQ消息来搜索目的地。为了减少RREQ泛洪报文带来的开销，只有网关和CHs转发RREQ报文。没有普通节点参与RREQ报文，集群间通信会向相关CH发送RREQ消息，并维护邻居表。

四、仿真结果与讨论

本文利用NS-2模拟器[9]进行仿真，验证了所提方法EDWCA与现有DWCA的性能。模拟结果中使用的节点数量在100到500个节点网络之间变化，节点随机分布在(750x750)米的区域内。模拟运行了450秒。集群大小固定为15。仿真设置和参数如表1所示。

—PDR (Packet Delivery Ratio)

“数据包发送比”指目的端接收到的数据包数与源端发送的数据包数的比值。当流量减少时，PDR总是高的，而当流量增加时，PDR就会降低。图3所示。显示与DWCA相比，即使在高流量情况下，EDWCA的交付率也很高。

延迟:

这是通过网络将数据从源传输到目的地所花费的时间。这取决于传输时网络中的流量。当模拟开始时，流量较少，所以延迟也最小，一段时间后，由于流量的增加，延迟也在所有网络中增加。图4所示。显示延迟传输数据包从源到目的地的现有和提出的方法。结果表明，EDWCA时延小于DWCA时延。

·能源消耗总量

图5所示。说明了DWCA和EDWCA的网络能耗。可以看出，采用EDWCA的网络能耗明显低于采用DWCA的网络。研究了采用SCH处理CH猝死情况和平衡CH负荷的机理。

•丢包

在各种情况下都会发生包丢包，

·由于介质拥塞，链路断裂。

由于传输队列中数据过多

由于缺乏能源资源

由于黑客的恶劣行为。

图6所示。在我们的实验中，由于上述原因，包丢量增加，但与DWCA相比，EDWCA的包丢量较小。

诉的结论

本文对分布式加权聚类算法(DWCA)进行了改进，提出了一种增强型分布式加权聚类算法(EDWCA)。如前所述，我们的算法通过使用SCH和Gateway节点来降低控制消息开销，从而提高了整体性能并降低了能源利用率。我们的协议在节能、丢包和PDR等所有性能指标上都比现有的DWCA有更好的结果。将来，该协议可以扩展到包括集群之间的组密钥管理，以提供收集数据的安全传输。我们还打算扩展聚类体系结构以支持MANET中的多跳聚类。通过应用EDWCA，有效地利用功率、带宽、稳定集群有助于提高MANET的服务质量。

表格一览

表1

数字一览

图1 图2 图3

图4 图5 图6

参考文献

1. 王嘉伟，“基于电池功率的移动Ad Hoc网络稳定聚类算法”，淡江科学与工程学报，Vol. 9, No . 3, pp. 233-242， (2006)
2. Naveen Chauhan等，“基于分布式加权集群的manet路由协议”，《无线传感器网络杂志》，第3卷，第54-60页，2011年
3. Wojciech Bednarczyk, Piotr Gajewskil，“一种基于加权参数的增强MANET聚类算法”，《通用通信与网络杂志》，第1卷，第3期，pp 88-94, 2013。
4. Sahar Adabi等，“一种新型的移动Adhoc网络分布式聚类算法”，计算机科学杂志，第4卷，第2期，pp: 161-166, 2008。
5. 拉尼V. G，普努萨瓦利M。“MPBCA:基于移动预测的MANET聚类算法”，中国机械工程学报，第5卷，第1期，pp: 303 -409, 2013。
6. Dahane Amne, Berrached Nassreddine和Kechar Bouabdellah，“移动传感器网络的节能和安全加权聚类算法”，第九届未来网络与通信国际会议(FNC 2014)， precdia计算机科学，pp: 63-70, 2014。
7. Muthuramalingam。陈志伟等，“一种基于移动预测的manet动态聚类算法”，计算机与电子工程学报，第2卷，第4期，pp 709-714, 2010。
8. 洪tzng - pei Wu - hsi，“一种改进的加权聚类算法确定异构传感器网络中的应用节点”，信息隐藏与多媒体信号处理，国际通用，第2卷，第2期，pp:173-184, 2011。
9. NS-2模拟器。可在线购买:http://www.isi.edu/nanam/ns