改进节点度分簇路由协议研究

◆李 琛 杨 松 于永学 裴小东

（海军装备研究院 北京 100036）

改进节点度分簇路由协议研究

◆李 琛 杨 松 于永学 裴小东

（海军装备研究院 北京 100036）

在移动自组网节点规模较大的情况下，采用基于分簇结构的路由协议。最高节点度簇首算法，能够减少自组网簇的数量，提高自组网组网效率，减少簇间路由开销。本文在该协议的基础上，对簇首的选择进行改进，考虑自组网节点位置和移动状态的变化导致簇首的频繁变更的问题，对最高节点度算法进行改进，提高网络拓扑的稳定性，降低节点路由维护开销。

移动自组网；分簇路由协议；节点度；簇首

0 引言

传统的有线网络中路由器固定，组网后网络拓扑稳定，路由信息可长时间不用更新。移动自组网是无固定基础设施、无中心的自组织网络，网内节点在移动状态下组网，组网具有灵活以及不受地理环境限制的优势，所有节点具备路由功能，节点可以随时加入或离开自组网而不会导致网络瘫痪，因此，移动自组网路由协议是保证组网稳定高效的关键技术之一。针对移动自组网不同网络规模和任务需求，已经发展大量的路由协议技术，其中在大规模节点情况下，普遍采用技术成熟的分簇路由协议实现高效组网。本文研究改进节点度的分簇路由协议，在原有最高节点算法的基础上对簇首变更提出改进方法，降低簇首变更频率，节省网络维护资源，提高网络拓扑稳定性。

1 分簇路由协议研究现状

图1 分簇结构示意图

分簇路由协议区别于平面路由协议。在平面路由协议中，所有组网节点地位平等，节点在功率覆盖范围内可以互联互通，距离较远则多跳传输。平面路由协议适合节点规模较小的自组网，路由信息更新快，路由建链维护方便，但是节点数目增多会导致路由开销大，造成网络资源浪费。分簇路由协议基于分簇结构的自组网，簇的划分主要根据网络中结构功能类似的节点进行划分，簇内包含一个簇首和若干簇成员，组网示意如图1所示。簇首一般根据最小ID、最高节点度、最低移动性、节点位置等条件进行选举，主要控制并管理簇内成员，协调簇成员报文传递，对簇内信息收集以及数据处理，将信息数据共享给其他簇首。分簇路由协议相比平面路由协议能够有效控制洪泛广播信息，簇成员功能相对简单，不需要维护复杂的路由信息，在跨簇传播时主要在簇首层级传播，网络规模不受限制，在大规模节点情况下能够实现降低节点能耗和提高网络通信质量的目的，但是簇首的维护比较复杂，在网络拓扑变化时，簇首的变更也会占据网络路由开销，而且，路由通过簇首寻路，因此所寻路径不一定是最优路径。

2 最高节点度分簇路由协议

在分簇路由协议中，一个节点与相连一跳距离的节点（邻居节点）数量称为节点度。最高节点度算法根据最大节点度对自组网进行划分。采用该算法的路由协议，将拥有最高节点度的节点选举为簇首，度数相同则随机选择节点作为簇首，簇首的邻居节点作为簇成员，簇首和簇成员一起组成簇，自组网对所有节点进行上述过程，直至所有节点身份确定。具体算法描述如下：

假设区域内存在N个节点，每个节点分配标识为1，2，3，…，N。任意节点通过广播问询的方式与其他节点交互信息，得到该问询信号的节点会向广播问询的节点发送应答信号，这样每个节点都会得到一个判决矩阵，公式如下：

式中，当第i节点与第j个节点不临相邻时，aij=0；当第i个节点与第j个节点相邻时，aij=1；同时定义i=j的情况下，aij=1。

判决矩阵A包含了本节点同其他节点的位置关系信息，反映了网络的拓扑结构。矩阵中主要由0和1两个元素构成，当aij=0时，表示节点i和j不相邻；当aij=1时，表示两节点相邻。在已经获得判决矩阵信息的情况下，可以计算每一个节点的节点度，再根据节点度对自组网进行分簇。

节点i的度数DN（i）计算公式如下：

式中i=1，2，3，…，N。

在计算最大节点度后，按照节点度数值高低的依次选举为簇首，选举簇首后，判决矩阵需对与簇首节点相连的邻居节点剔除判决矩阵，再重新选举其他簇首。计算形式如下：

定义，第k个节点的度数为DN（k），公式如下：

节点k为第1个簇首H1，将DN（k）记录并保存到选举度S（k）=DN（k）中。令k’ ∈V-Ntotal（i），i’ ∈V-Ntotal（i），继续在剩余节点中选择簇首，公式如下：

节点k’被选为第2个簇首H2，保存选举度S（k’），用同样的方法继续选择簇首，直到自组网分簇完毕。

按照最高节点度算法将自组网划分为不同簇区域，能够尽量减少自组网簇的数目。业务报文簇内转发概率增加，簇间转发效率提高，从系统整体上有效降低传输时延。但是，基于最高节点度的分簇算法，簇首变更频繁，引发大量维护开销，造成网络资源浪费。

3 改进节点度分簇路由协议

改进节点度分簇路由协议主要针对原协议簇首变更频繁的问题，在设计时引入门阈值T，既降低簇首变更频率，同时能够在拓扑结构变化较大时及时变更簇首，提高系统效率。改进节点度分簇路由协议主要包括分簇的建立和维护两部分内容。

3.1 分簇建立

改进节点度分簇路由协议在组网之初，采用最大节点度算法的思路，尽可能减少组网簇首的数量，具体算法如下。

通过广播问询以及统计应答信息，建立判决矩阵A：

其中判决矩阵A中，当i=j时，aij=1。N为节点总数量，所有节点从1到N对应不同序号进行标识；aij表示第i个节点与第j个节点的位置关系，当aij=0时，表示节点i和j不相邻；当aij=1时，表示两节点相邻。

根据判决矩阵计算节点度：

公式中ai代表第i个节点。计算所有节点度后，得到节点度矩阵DN，并根据节点度矩阵选取其中节点度最大的节点，作为簇首。

第一个簇首节点记为H1，节点度为：

对簇首选举度S（H1）进行赋值并保存选举度在本节点：

簇首决定后，该节点ai根据判决矩阵A中第i行中的值判断与簇首相连节点的位置关系。aij=1代表与簇首相连的邻居节点，这些作为簇成员不参与其他簇首选举，簇与簇成员组成簇；aij=0表示其他节点不与簇首ai一跳相连，参与其他簇首选举。簇确定后，需要根据判决矩阵从所有节点集合N中删除簇和簇成员节点，该簇节点集合定义为J，表示为：

剩余节点集合定义为N’，表示如下：

第二个簇首节点记为H2，需要在剩余节点集合中选取簇首，节点度为：

对簇首选举度S（H2）进行赋值并保存选举度在簇首节点H2中：

簇首选举之后，同样根据判决矩阵完成簇成员身份确定，完成第二个簇的建立，并从N’中删除簇首和簇成员集合，继续进行簇首选举，直至所有节点身份确定，完成组网过程。

3.2 路由维护

3.2.1 变更判决

组网完成之初，采用最大节点度算法的分簇网络保证簇首节点数量尽可能小。但是，由于移动自组网的移动性和开放性，节点位置可能不断变化，普通节点可能随时加入自组网，网络拓扑动态变化。原路由协议在网络拓扑变化后，始终根据节点度进行分簇，在节点移动速度快的情况下，可能引起簇首不断变更，虽然能够保证网络效率，却导致系统大量的路由维护。

采用改进节点度路由协议维护路由过程中，当簇首ai节点度变化时，计算当前节点度DN（ai），并与簇首保存选举度S做差运算，引入比较门阈值T，降低簇首变更骤然性，增加变更条件余量。

若簇首节点度满足如下条件：

则不需要变更簇首，即便簇内存在节点度大于簇首的簇成员，系统依然保持簇结构，保证网络稳定性，反之，则进入簇变更程序。

公式中，门阈值T的取值，根据自组网业务量多少和节点设备功率、传输能力等进行预先设置。在系统业务量繁重或者节点设备功率大、功能全面等情况下，可以将T的取值增大，减少簇首变更，维持自组网拓扑结构，反之，则减少T的取值，及时变更簇首，调整到系统最佳状态，提高系统效率。

3.2.2 状态变更

在改进节点度的路由协议中，节点状态（c_state）包括4种状态：簇首状态（CH）、成员节点状态（MEMBER）、网关状态（GW）、簇首竞争状态（CH_READY）。几种状态变更示意图如图2所示。

图2 状态转换示意图

（1）簇首状态

簇首与邻居节点以一跳距离相连，组成簇，簇与簇之间通过簇首相连。在其他节点加入该簇或者本簇节点离开该簇，簇首节点度变更超过阈值，进行变更，重新计算簇内节点节点度，若原簇首仍适合作为簇首状态，则不作改变，若连续3个周期存在簇首竞争状态，则将簇首竞争状态节点作为簇首，原簇首降为成员节点状态，并在本簇范围内广播发送强制变更消息。

（2）成员节点状态

成员节点状态是簇内可以随时作为其他状态的节点。

在当前拓扑更新周期内，若新增处于CH状态的双向邻居、且该CH所在簇的容量未满时，加入该CH所在的簇；若本节点的邻居中CH数量＞1，则成为网关节点，转入GW状态。

节点加入某簇的情况下，在当前拓扑更新周期内，若新增处于CH_READY状态的双向邻居，当本节点更适合作为CH时，进入CH_READY状态。

节点加入某簇的情况下，若在当前拓扑更新周期内，只收到处于双向MEMBER状态的节点发来的邻居通告，比较本节点及所有邻居的节点度，若本节点更适合作为CH，转入CH_READY状态。

节点尚未加入任何簇的情况下，若连续3个周期未收到处于CH_READY状态的节点发送的邻居通告，则自动转入CH_READY状态。

（3）簇首竞争状态

在当前拓扑更新周期内，若新增处于CH状态的双向邻居、且该CH所在簇的容量未满时，则加入该CH所在的簇，并转入MEMBER状态。

在当前拓扑更新周期内，若新增处于CH_READY状态的双向邻居，当对方更适合作为CH时，本节点转入MEMBER状态。

本节点若连续2个周期处于CH_READY状态，则表示竞争簇首成功，进入CH状态，并将此时的节点度记为选举度S。

（4）网关状态

在当前拓扑更新周期内，若新增处于CH状态的双向邻居、且该CH所在簇的容量未满时，加入该CH所在的簇，作为该簇的网关。

当本节点邻居中的CH数量降为1时，不再充当网关，转入MEMBER状态。

当本网关与相邻的成员节点或网关节点所属簇首不同时，相邻的成员节点或网关节点则成为本网关的协作网关节点。

3.3 路由协议过程

改进节点度分簇路由协议主要包含两部分内容：簇内路由过程和簇间路由过程。

（1）簇内路由过程

节点收到上层的单播业务请求，目的节点位于簇内时，直接查询簇内路由表，若存在到达目的节点的一跳路径，则选取簇内路由表中最小的路径作为传输路径；若不存在，选取路由表中最小的两跳路径作为传输路径（必然存在簇首作为中转节点的传输路径），然后，将传输路径写入业务报文首部。

（2）簇间路由过程

节点收到上层的单播业务报文请求，目的节点位于簇外时，通过查询网关列表、簇间路由表，若存在可用路由，则将传输路径写入业务报文首部，进行报文传递。若查询后不存在可用路径，生成路由请求RREQ消息。查询路由请求表后，将路由请求消息传递给目的节点，目的节点生成应答消息RREP，生成“本地-目的节点”的路由加入簇间路由表，完成簇间路由。

4 仿真与结果分析

设计路由协议可以更好的构造一个高效率的自组网，分簇路由协议主要应用节点较多的场合，分簇算法将自组网分成多个簇，算法的好坏直接影响移动自组网性能。本研究采用OPNET软件进行仿真验证。本论文研究的改进节点度分簇路由协议，主要在不同节点移动速度的情况下，对该协议和原有路由协议进行比较。在仿真过程中，门阈值统一设为T=2，设定其他参数一致的前提下，比较二者簇首变更频率的不同，传输时延的不同。仿真具体参数设置如仿真模拟实验参数表1所示。

图3 簇首变更率示意图

图4 不同节点移动速度下的传输时延

5 总结

本文基于最高节点度算法路由协议，提出改进节点度路由协议，对簇首的变更条件进行改进，并给出详细算法，从理论和初步试验证明了改进节点度分簇路由协议在簇首变更频率和传输时延方面对自组网性能的提高。

[1]臧小东．Ad Hoc网络路由协议的改进研究[学位论文]．南京邮电大学，2013．

[2]刘凯歌．基于分簇结构的Ad Hoc网络路由协议的研究与仿真[学位论文]．武汉理工大学，2007．

[3]LIN CR，GERLAM．Adaptive clustering formobile wire -less networks [ J ]．IEEE Journal on Selected Areas in Communications，1997．

[4]郑少仁，王海涛．Ad Hoc网络技术[ M ]．北京：人民邮电出版社，2005．

[5]陈敏．OPNET 网络仿真．北京：清华大学出版社，2004．

[6] Jiang M，Li J，Tay Y．Cluster based routing Protoeol（CBRP）funetional specification[Z]．IETF Intemet-Draft，Aug 1998．

[7]倪旻明．移动Ad Hoc网络中分簇组网技术的研究[D]．[博士学位论文]．北京：北京交通大学，2012．

[8]Ali Aydin M,Halim Zaim A,Gokhan Ceylan K．A hybrid intrusion detection system design for computer network security[J]．Computers & Electrical Engineering，2009．

Libpcap对数据的捕获是通过几个主要函数来完成的。首先调用Pcap-lookupdev()函数找到查找可以捕获数据包的设备接口，并返回该网络设备名称。接着调用Pcap-open()函数，利用上面查询到的接口设备创建捕获句柄，进行数据捕获并将捕获的数据转换成以太类型，分析判断包含的数据包类型。

Sebek和Libpcap都是在Linux系统内核中完成的，可以在不同的层次把两者结合起来进行多层次数据捕获，保证了数据捕获的全面性和可靠性。

3 结论

本文设计的数据捕获系统是基于Linux系统内核的基础上对传统Honeypot数据捕获的一种改进，采用双层捕获机制，能名够尽可能地对数据包的全面、可靠性捕获，从而进行深入分析，获取攻击者的信息，以便更有效保护好主机系统。

参考文献：

[1]朱一帅，吴礼发．基于Sebek的蜜罐识别机制研究[J]．信息技术，2009．

[2]陈超，妙全兴．蜜罐识别与反识别技术研究[J]．计算机安全，2009．

[3]田俊峰，刘永立．一种新的蜜网模型——BRHNS[J]．计算机工程与应用，2007．

湖南省教育厅科研基金项目，项目编号：15C0166。