目前，根据更新机制的不同[3-4]，路由协议大致可以分为表驱动(主动)路由、按需(被动)路由、混合路由和地理路由4种路由策略。主动路由周期性地广播路由信息来维护路由，路由信息的周期性交换需要消耗大量的带宽资源，因此此类协议适合较小规模的网络；被动路由不需周期性地广播路由信息，只有在源、目的节点通信需要且该链路不为源节点所知时才进行路由发现过程，路由发现会造成一定的时延，因此此类协议也适合规模较小、节点移动性较大的网络；混和路由协议则是由主动路由和被动路由有机结合组成的协议，即在一定的网络区域内采用主动策略，区域间则采用被动策略，此类协议主要针对规模较大、移动性较强的网络所设计；地理路由是随着GPS、北斗等定位技术的不断发展带来的产物，在MANETs节点上装备定位装置，节点可以准确获得自己的地理位置和时标，据此，源节点可将数据“有目的”地向目的节点的方向上传输，最终到达目的节点。
根据网络的逻辑视图，路由协议可以分为平面路由协议和分簇路由协议2种。在平面路由协议中[5-6]，网络中所有的节点地位平等，功能也都相同，节点之间通常采用单一的路由策略，因此比较容易实现。但是MANETs中节点的随机移动性、加入或离开网络的不可预测性等特点引起的网络拓扑结构的频繁变化，可能会导致通信节点间路由的频繁失效，通信节点间重新建立起有效的通信路径可能会导致较长的时延和较大的网络开销，限制了网络的规模。
分簇路由协议[7-10]的提出有效解决了平面路由中时延长和网络开销大等问题，非常适用于大规模MANETs。在分簇路由协议中，网络按照某种特定的规则将网络节点划分成不同的簇，每个簇按特定规则选举产生簇首，相邻簇间通信时通过网关节点进行转发，而对转发后数据如何到达目的节点的细节并不关心。分簇路由协议不仅可以减少参与路由维护的节点数目，还可以降低因路由信息交换带来的网络开销，而且采用特定的分簇策略将网络划分成不同的稳定子网络，可以降低网络拓扑的动态变化对路由协议性能的影响，极大地提高了网络的通信效率。
ZRP[11]是第一个混合使用主动驱动和被动策略的自组织网络分簇路由协议，其规定在区域内采用DVA主动路由策略，区域间则采用类似DSR协议中的被动路由机制。ZHLS和SLURP等协议[12]也采用类似ZRP协议的策略，区域内采用主动路由机制，区域间采用被动路由机制。它们有一个共同缺点，就是数据流量较大(特别是参与通信的节点较多)时，路由发现将消耗大量的网络带宽，严重时将会导致网络瘫痪。同时，频繁的路由发现过程也会造成一定的传输时延，影响数据的时效性。CBRP[13]等协议不论是在簇内还是簇间均采用被动路由策略，因此路由发现的时间较长，且当网络流量较小时，消耗的网络带宽也小，但随着流量的逐渐增大也会占用大量的网络带宽，影响网络的整体性能。HSR和CGSR[14-15]等协议则在簇内和簇间都使用主动路由机制，虽然降低了路由发现所需的时延，但大大增加了网络的控制开销，因此这类协议适用于节点移动速度较小的网络。
在分簇路由协议中，分簇机制作为网络拓扑管理的一种有效模式，不仅可以降低网络管理的复杂度，而且还很好地提高了MANETs的扩展性。因此，合理有效的分簇机制对于分簇类路由协议来说至关重要。文献[16-19]详细介绍了现有的一些分簇算法，但主要是针对一些特定的需求，例如最小ID簇和最大连通度算法等。文献[20]提出了一种动态多普勒分簇(Dynamic Doppler Velocity Clustering，DDVC)算法和动态链路持续时间分簇(Dynamic Link Duration Clustering，DLDC)算法，二者都只适合于网络节点具有伪线性运动轨迹的高速MANETs。文献[21]提出了一种利用连续2次发送Hello消息的多普勒频移计算节点移动速度的MPBC算法，该算法将与所有邻居节点的移动特性具有最大相似度的节点选举为簇首。
基于此，本文提出了一种基于联合度量指标Tm的分簇算法。仿真结果表明：Tm分簇算法通过提高簇内节点的数目，减少了簇成员在簇间的切换次数，提高了分簇算法的稳定性。同时还在该分簇算法的基础上提出了一种新的分簇路由协议Tm-R。仿真结果表明：Tm-R分簇路由协议较其他4种典型协议降低了网络的平均端到端时延和平均路由开销，并增加了数据包接收的成功率。
1 分簇算法 1.1 分簇度量指标
1.1.1 链路保持时间 假定MANETs中的每个网络节点都按照三维Gauss-Markov模型移动[22]，节点的最大通信半径均为r，任意2个节点之间可实现双向通信，而且每个网络节点都能通过GPS或北斗卫星实时获得自身的地理位置和时间信息，并周期性地向其相邻节点发送自己的最新坐标和时间信息，据此可大致预测出每条链路的保持时间。
设节点i前后2次向其邻居节点j发送自己的时间和坐标信息，分别为t1,(xi1,yi1)和t2,(xi2,yi2)，且在t1和t2时刻，节点j的坐标信息分别为(xj1,yj1)和(xj2,yj2)。在实际网络中，节点i和节点j都是移动的，为简化分析，在此假定节点i固定，节点j移动。图 1(a)为节点i和节点j相互“远离”的情形，图 1(b)为节点i和节点j相互“接近”的情形。
 |
| 图 1 链路保持时间示意图 Fig. 1 Sketch map of link holding time |
| 图选项 |
在图 1中，节点i固定在坐标原点O，而节点j相对节点i由A点沿向量AB的方向移动。假定在Δt=t2－t1时间内，节点i和节点j运动速度和方向都保持不变，经过时段Δt，节点j由A点运动到B点。
图 1(a)中有如下关系成立：
 | (1) |
 | (2) |
由余弦定理可得
 | (3) |
式中：
则节点i和节点n之间的相对移动速度为
 | (4) |
由于Δt时间内，节点i和节点j运动速度和方向都假定保持不变，因此，图 1中节点j脱离节点i(即飞出节点i的通信范围)所需的运动轨迹为线段BC。即从时刻t2开始算起，节点i和节点j之间的链路还可以继续保持的时间为
 | (5) |
式中：
 |
图 1(b)的分析方法与图 1(a)类似，同理可得
 | (6) |
式中：dOA和dOB定义与图 1(a)相同。
 |
1.1.2 移动性因子 为度量节点的移动性因子，引入远隔性函数[23-24]的概念。远隔性是节点移动性的一种标准度量。
假定网络中共有N个节点，ni(t)表示节点i在t时刻的位置向量，i=1,2,…,N，则在t时刻节点i和节点j之间的距离可以定义为
 | (7) |
因此，t时刻节点i到节点j的远隔性可定义为
 | (8) |
式中：F(·)为关于距离的函数。通常，最简单的F(·)函数是恒等函数，即
 | (9) |
远隔性是随着节点的动态移动而实时改变的，因此移动性因子应该根据远隔性的时间倒数来计算，即移动性因子Mi(t)为
 | (10) |
将式(9)代入式(10)得
 | (11) |
式中：t2－t1→0。
继续沿用图 1的假设，因此无论是节点i和节点j相互“远离”还是“靠近”，式(11)都可简化为
 | (12) |
1.1.3 联合度量指标 在设计MANETs分簇算法时，本文将链路的保持时间和节点的移动特性有机结合起来作为网络分簇时选择簇首的联合度量指标，即
 | (13) |
式中：Tij为选择节点i作为簇首时，节点i与邻居节点j之间链路的保持时间；Mi为节点i的移动性因子。
1.2 分簇策略
1.2.1 簇的初始化 当MANETs刚建立时，所有的网络节点都处于孤立状态。每个节点首先按照式(13)计算其成为簇首节点的联合度量指标，然后向其一跳邻居节点发送包含该联合度量指标的Hello消息，当邻居节点收到Hello消息后，将其值与自己的联合度量指标相比较，将联合度量指标较大的节点选举为簇首，并将其簇首声明信息广播给它的所有一跳邻居节点。当邻居节点收到簇首声明信息之后，则向其发送加入请求信息，当簇首收到加入请求消息并“同意”该邻居节点成为其簇成员时，将向该邻居节点发送一个请求接受消息，当邻居节点收到该请求接受消息之后即意味着其成功加入到该簇中，该邻居节点就会周期性地广播一个成员信息来宣告自己的存在状态，同时簇首也会周期性地发送一个簇首信息来维护其“统治地位”。
1.2.2 网关的选择 如果网络节点在发送加入请求消息之后，收到2个或2个以上的请求接受消息，则表明该网络节点处于2个或多个簇的相交地带，因此可将其选举为网关节点。
1.2.3 簇的维护 簇完成初始化之后，簇首和簇成员之间必须周期性地交换包含各自ID号的信息来维护 “友好”关系。当MANETs的拓扑结构发生变化时，本文分以下3种情形来确保网络划分成合适的簇。
1) 删除或增加节点
当簇成员收不到簇首周期性广播的包含簇首ID的信息或簇首收不到簇成员周期性广播的包含簇成员ID的信息，表明该节点已不在该簇中，则将其信息从该簇中删除。
当新节点(包括新加入网络的节点或被其他簇剔除的节点)想要加入一个簇中时，就必须周期性地广播一个加入请求信息，当某簇簇首收到该消息后，若同意其加入，则向该节点发送一个加入接受消息，新节点收到该加入接受消息后正式成为该簇中的成员。
2) 簇首的更换
如果某簇的簇首离开该簇或失效时，与其相关联的邻居节点就会重新变成孤立节点，因此这些孤立节点必须重新周期性地广播加入请求消息，如果某些孤立节点收到过多的加入请求消息，则表明这些孤立节点附近不存在簇首，因此必须重启簇的初始化过程。
3) 簇的合并
如果2个簇进入到彼此的通信范围，并且2个簇首之间的联合度量指标相差不大，则表明2个簇会在相互的范围内停留较长的时间，这意味着二者合并的可能较大，因此值得合并这2个分簇。原来联合度量指标较小的簇首则成为合成新簇的簇首，原来联合度量指标较大的簇首则变为普通簇成员。如2个簇首之间的联合度量指标相差很大，表明这2个簇只是“擦肩而过”，不需要合并。
2 分簇路由协议 通常，分簇路由协议可以降低大规模网络的路由开销，即通常簇内采用源路由策略，簇间采用被动路由策略，其伪代码如下:
if source and destination in the same cluster
{if dsd is small than twice of transmission range
Node source and destination communicate directly
else
Node source and destination communicate via relay
}
else
{L1:Node source send RREQ to neighbor clusterhead via gateway
if destination is in the neighbor cluster
Node destination RREP to source along the coming way
else
goto L1;
}
2.1 簇内通信 当源、目的节点处于同一分簇时，两节点之间可以直接通信或者通过该分簇的簇首中继转发。即当目的节点处于源节点的通信覆盖范围时，两节点可直接或通过簇首中继转发来完成通信任务；否则，只有通过簇首的转发才能完成数据传输。
2.2 簇间通信 当源、目的节点不在同一簇中时，源节点就会发起簇间路由策略。首先，源节点向其所在簇的簇首发送请求消息，该簇首收到请求消息后，通过网关节点将其转发给相邻簇的簇首。当目的节点所在分簇的簇首收到该消息后，就会沿着发送请求消息相反的路径发送应答消息。处于该反向路径上的簇首收到该应答消息后，会根据当前链路状态选择局部最短路径向下继续传递该应答消息。因此，源节点最终会获得通往目的节点的最短路径。
2.3 路由维护 由于MANETs中节点的高速移动性，网络的拓扑结构也在快速的变化当中，已建立链路极可能中断。因此，高效的路由维护机制对保障协议的时效性等方面至关重要。当网络中某条链路中断后，网络就会进行局部修复，即用中断节点间的一条最短路径替换中断路径，然后进行路径更新并将修复后的结果告知给目的节点。
由于簇首周期性进行路由维护，因此为确保簇间路由的时效性，只有当簇间链路发生中断时才发起局部链路修复工作。这种局部链路修复技术对减少路径重建开销和端到端时延非常有效。
3 性能分析 本文利用NS3网络仿真软件对动态分簇算法和分簇路由协议的性能进行仿真分析。网络中各移动节点随机分布在300km×300km空域范围内，且按照Gauss-Markov移动模型移动，节点的传播范围为15km，速度为50~100m/s之间的随机值，仿真时间设为60min。
仿真中，每个节点的仿真模型均相同。物理层采用自由空间模型，并考虑实际航空通信的物理参数，如发射功率和接收机灵敏度等；MAC层采用TDMA协议；网络层采用分簇路由协议(簇内采用OLSR，簇间采用AOVD)；应用层采用均匀分布的恒定比特业务。网络成员以相同概率产生新的业务且持续时间服从负指数分布，数据包长度服从泊松分布。参数设置如表 1所示。
表 1 仿真参数设置 Table 1 Simulation parameter setting
| 参数 | 数值 |
| 信道速率/(Mb·s-1) | 5 |
| 数据包平均大小/KB | 512 |
| 发射功率/W | 125 |
| 接收机灵敏度/dBm | -24.67 |
| 物理层特征 | 直接序列扩频(DSSS) |
表选项
3.1 分簇算法仿真对比与分析 在分簇路由协议中，网络控制开销主要来源于分簇的过程和簇间的信息交换，因此分簇时产生的簇越少，相应地网络开销也会减少。并且，由于MANETs拓扑结构不断发生变化，原来属于本簇的簇成员很可能离开本簇而加入到另外的一个簇中去，若这种情形频繁发生，则会严重影响网络的性能。
综上，本文将用簇的数量和簇间切换次数这2个指标来衡量分簇算法的优劣，并将本文提出的分簇算法与现有DLDC、DDVC、MPBC和MOBIC算法进行比较分析。
图 2反映了网络节点数对簇数量的影响。可以看出，当网络节点的数量增加时，Tm、DLDC、DDVC、MPBC和MOBIC这5种算法所形成的簇的数量都在减少，但Tm分簇算法充分考虑了节点间链路的保持时间和移动性因子，因而形成的簇的数量相对较少且稳定。
 |
| 图 2 节点数量对簇数量的影响 Fig. 2 Influence of nodes’ number on cluster’s number |
| 图选项 |
图 3反映了网络节点数对簇间切换次数的影响。当网络节点的数量增加时，节点之间的平均距离在逐渐缩短，而节点的通信范围固定不变，因此节点通信覆盖范围内的节点数必将增加，这就会带来频繁的拓扑结构变化和通信链路的断开与连接。如图 3所示，由于当节点数量增加时，Tm分簇算法形成的簇较少，因此在相同的网络规模下，簇内节点的数量就会相对较多，簇内成员的簇间切换的次数也会相继减少。因此相比其他4种分簇算法，Tm分簇算法具有更好的稳定性。
 |
| 图 3 节点数量对簇间切换次数的影响 Fig. 3 Influence of nodes’number on nodes’ switch times between clusters |
| 图选项 |
3.2 分簇路由协议仿真对比与分析 为评估Tm-R分簇路由协议的性能，本文将其与现有的MPBC-R、DLDC-R、DDVC-R和MOBIC-R协议从平均端到端时延、平均路由开销和丢包率3个方面进行仿真对比。
显然，当节点的数量增加时，平均端到端时延必然会增加。这是因为当节点数量增加后，网络中参与通信的节点的数量也随之增加，这样就会消耗更多的带宽，也势必会增加多跳节点对之间通信的可能，因此平均端到端时延会迅速增大。图 4反映了节点数量对网络平均端到端时延的影响。可以看出，Tm-R分簇路由协议的平均端到端时延低于其他4种分簇路由协议。这是因为Tm-R分簇路由协议在分簇时更为精确地考虑了节点间链路的保持时间，因此形成的簇最为稳定，进而避免了不必要的时间浪费。
 |
| 图 4 节点数量对平均端到端时延的影响 Fig. 4 Influence of nodes’ number on average end-to-end delay |
| 图选项 |
图 5反映了节点数量对平均路由开销的影响。网络的路由开销主要包括路由重建和路由维护所产生的控制消息数据包。显然，当网络中的节点数量增多时，网络的平均路由开销必然会增加，这与图 5所示相符。但由于本文提出的Tm-R分簇路由协议具有稳定的分簇机制，簇的重建和簇间切换的概率相对其他4种协议较低，不需要过多的路由建立和维护控制数据包的传输，因此路由开销较小。
 |
| 图 5 节点数量对平均路由开销的影响 Fig. 5 Influence of nodes’ number on normalized routing overhead |
| 图选项 |
图 6反映了节点的最大移动速度对数据包接收成功率的影响。可以看出，当节点的最大移动速度增加时，数据包的接收成功率随之降低。这是因为节点移动速度的增加势必会造成网络拓扑结构的频繁变化，这就会增加节点间原有链路“失联”的概率，因此造成了更多的丢包。由于Tm-R分簇路由协议的分簇机制较其他协议最为稳定，因此其数据接收成功率最高。
 |
| 图 6 最大移动速度对数据包接收成功率的影响 Fig. 6 Influence of maximum movement speed on packet acceptance ratio |
| 图选项 |
4 结 论 在分析现有分簇算法和分簇路由协议特点的基础上，提出了一种新的分簇算法和分簇路由协议，仿真结果表明：
1) 该分簇算法具有良好的稳定性。
2) 基于此分簇算法的分簇路由协议较其他4种典型分簇路由协议，降低了整个网络的平均端到端时延和平均路由开销，并提高了数据包接收的成功率。
参考文献
| [1] | JAWHAR I, WU J. QoS support in TDMA-based mobile Ad Hoc networks[J].Journal of Computer Science and Technology, 2005, 20(6): 797–810.DOI:10.1007/s11390-005-0797-3 |
| [2] | KUMAR S, RAGHAVAN V S, DENG J. Medium access control protocols for Ad Hoc wireless networks[J].Ad Hoc Networks, 2006, 4(3): 326–358.DOI:10.1016/j.adhoc.2004.10.001 |
| [3] | GAVRILOVSKA L,ATANASOVSKI V.Ad Hoc networking towards 4G:Challenges and QoS solutions[C]//7th International Conference on Telecommunications in Modern Satellite,Cable and Broadcasting Services.Piscataway,NJ:IEEE Press,2005:71-80. |
| [4] | BEN MAHMOUD M S,LARRIEU N.An ADS-B based secure geographical routing protocol for aeronautical Ad Hoc networks[C]//2013 IEEE 37th Anmual Computer Software and Applications Conference Workshops.Piscataway,NJ:IEEE Press,2013:556-562. |
| [5] | SANTHI K,PARVATHAVARTHINI B.Randomized routing techniques for Ad-Hoc on-demand distance vector of wireless networks[C]//2013 International Conference on Human Computer Interactions (ICHCI).Piscataway,NJ:IEEE Press,2013:1-6. |
| [6] | ISTIKMAL.Analysis and evaluation optimization dynamic source routing (DSR) protocol in mobile Ad Hoc network based on ant algorithm[C]//2013 International Conference of Information and Communication Technology(ICoICT).Piscataway,NJ:IEEE Press,2013:400-404. |
| [7] | NIU X,TAO Z,WU G,et al.Hybrid cluster routing:An efficient routing protocol for mobile Ad Hoc networks[C]//2006 IEEE International Conference on Communications.Piscataway,NJ:IEEE Press,2006:3554-3559. |
| [8] | WOO S C, SINGH S. Scalable routing protocol for Ad Hoc networks[J].Wireless Networks, 2001, 7(5): 513–529.DOI:10.1023/A:1016726711167 |
| [9] | ZHOU J H,LEI L,LIU W K,et al.A simulation analysis of nodes mobility and traffic load aware routing strategy in aeronautical Ad Hoc networks[C]//Proceedings of 2012 9th International Bhurban Conference on Applied Sciences and Technology.Piscataway,NJ:IEEE Press,2012:423-426. |
| [10] | HYEON S,KIM K,YANG S.A new geographic routing protocol for aircraft Ad Hoc networks[C]//2010 IEEE/AIAA 29th Digital Avionics Systems Conference.Piscataway,NJ:IEEE Press,2010:255-260. |
| [11] | DUBE R, RAIS C D, WANG K Y, et al. Signal stability based adaptive routing for Ad Hoc mobile networks[J].IEEE Personal Communications Magazine, 1997, 4(1): 36–45.DOI:10.1109/98.575990 |
| [12] | NG J M, LU I. A peer-to-peer zone-based two-level link state routing for mobile Ad Hoc networks[J].IEEE Journal on Selected Areas in Communications, 1999, 17(8): 1415–1425.DOI:10.1109/49.779923 |
| [13] | WANG Y, DONG L, LIANG T T, et al. Cluster-based location aided routing algorithm for mobile Ad Hoc networks[J].Journal of Software, 2009, 11(20): 3086–3100. |
| [14] | PEI G,GERLA M,HONG X,et al.A wireless hierarchical routing protocol with group mobility[C]//1999 IEEE Wireless Communications and Networking Conference.Piscataway,NJ:IEEE Press,1999:1538-1542. |
| [15] | CHIANG C C,WU H K,LIU W,et al.Routing in clustered multihop,mobile wireless networks with fading channel[C]//1997 IEEE Singapore International Conference on Networks-Networks:The Next Millennium.Piscataway,NJ:IEEE Press,1997:197-211. |
| [16] | YU J Y, CHONG P H J. A survey of clustering schemes for mobile Ad Hoc networks[J].IEEE Communications Surveys and Tutorials, 2005, 7(1): 32–48.DOI:10.1109/COMST.2005.1423333 |
| [17] | ABOLHASAN M, WYSOCKI T, DUTKIEWICZ E. A review of routing protocols for mobile Ad Hoc networks[J].Ad Hoc Networks, 2004, 2(1): 1–22.DOI:10.1016/S1570-8705(03)00043-X |
| [18] | MEHTA S,SHARMA P,KOTECHA K.A survey on various cluster head election algorithms for MANET[C]//2011 Nirma University International Conference on Engineering.Piscataway,NJ:IEEE Press,2011:1-6. |
| [19] | VENKATESWARAN A,SARANGAN V,GAUTAM N,et al.Impact of mobility prediction on the temporal stability of MANET clustering algorithms[C]//International Workshop on Modeling Analysis and Simulation of Wireless and Mobile System.New York:ACM,2005:144-151.http://cn.bing.com/academic/profile?id=2113662123&encoded=0&v=paper_preview&mkt=zh-cn |
| [20] | SAKHAEE E, JAMALIPOUR A. Stable clustering and communications in pseudolinear highly mobile Ad Hoc networks[J].IEEE Transactions on Vehicular Technology, 2008, 57(6): 3769–3777.DOI:10.1109/TVT.2008.919606 |
| [21] | NI M M, ZHONG Z D, ZHAO D M. MPBC:A mobility prediction-based clustering scheme for Ad Hoc networks[J].IEEE Transactions on Vehicular Technology, 2011, 60(9): 4549–4559.DOI:10.1109/TVT.2011.2172473 |
| [22] | YU J Y, CHONG P H J. An efficient clustering scheme for large and dense mobile Ad Hoc networks (MANETs)[J].Computer Communications, 2006, 30(1): 5–6.DOI:10.1016/j.comcom.2006.07.014 |
| [23] | NG J M,ZHANG Y.A mobility model with group partitioning for wireless Ad Hoc networks[C]//3rd International Conference on Information Technology and Applications.Piscataway,NJ:IEEE Press,2005:289-294. |
| [24] | XU K,HONG X,GERLA M.An Ad Hoc network with mobile backbones[C]//IEEE International Conference on Communications.Piscataway,NJ:IEEE Press,2002:3138-3143. |
