改进最小生成树算法在移动自组织网络路由选择中的应用

张　娜

(铁岭师范高等专科学校， 辽宁 铁岭 112001)



改进最小生成树算法在移动自组织网络路由选择中的应用

张娜

(铁岭师范高等专科学校， 辽宁 铁岭 112001)

摘要:针对移动自组织网络的动态性和多跳网络特性，在路由选择中提出改进最小生成树算法.设计过程中既考虑节点间的直通中断概率，又考虑多跳次数对信道容量的影响，通过调整最小生成树得到源节点与目的节点间最佳路由.实验结果表明：改进最小生成树算法可以获得更高的信道容量.

关键词：改进最小生成树算法；移动自组织网络；路由选择

移动自组织网络是一种多跳的临时性自治系统，在移动自组织网络中，网络中的节点通过中继的方式连接，网络拓扑结构经常变化.因为节点状态可能随时改变，通信信道也没有传统的固定基站稳定，导致移动终端间的网络拓扑结构随时可能发生变化[1].移动自组织网络是一种临时的、自治的、多跳的分布式网络，没有固定的基站支持通信，两个节点之间的通信通过网络中的节点进行信息转发来完成，网络中没有中心节点或者严格的控制节点，所有节点地位平等，节点的功能随状态改变，通信路径随节点的改变进行调整，整体网络信息的传递不会受任何节点故障影响.在移动自组织网络中，通信路径随节点的状态改变，其优点是：不需要固定的基站支持通信；多跳网络各个节点不需要直接连接，而是能够通过中继方式实现两个距离很远无法直接通信的节点之间传递信息.移动自组织网络在军事通信、移动网络、紧急服务、灾难恢复、无线传感器网络等领域中都具有广泛的应用前景.

选择合适的路由技术能够以较低的通信负担和计算负担来获得路由，而移动自组织网络因为其具有动态性、多跳传输性，使得传统的路由选择技术在移动自组织网络中无法直接使用，因此，研究新的适合移动自组织网络特性的路由技术具有重要意义.

1路由选择机制与分类

1.1路由选择机制

路由选择是指在互联网络中选择从源节点到目标节点的传输信息通道，在信息通道中信息至少通过一个中间节点[2].路由选择的主要工作是在OSI网络参考模型中的网络层.在路由选择过程中包含两个基本的操作：最佳路径选择和网间信息的传递.路由选择策略有两个考虑因素：一个为网络的通信量，选择通信量相对较小的路径以避免拥塞；另一个为网络的拓扑结构，随时掌握网络的拓扑结构，不能选择一个不工作的路由器作为数据的下一跳路由器.

1.2路由选择分类

路由选择策略主要是选择节点间的路径，根据选择方式的不同分为：静态路由选择和动态路由选择[3].静态路由选择是事先计算好路由选择，网络启动时加载到路由器中，不再变化.静态路由选择策略有：

(1) 固定式路由选择：固定式路由选择中网络中的每一对节点都有一个固定的路径，路径存储在各节点中的路由表中，当网络拓扑结构发生改变时路由表也随之改变.当信息从源节点传递到某中间节点时，通过查找该节点路由表，就可以知道要转发的下一节点地址.

(2) 洪泛路由选择：又叫扩散法，一个分组由源节点发送到与其相邻的所有节点，收到的节点再次将分组传输到除分组经过的节点以外的所有节点.当某一个信息分组首先到达目标节点时，则该信息分组经历的路径最短，其主要应用在诸如军事网络等对强壮性要求很高的场合.

(3) 随机路由选择：一个分组从源节点发送时只选择一条路径进行传输，选择的路径是随机的或者采用轮询的方式.

动态路由选择策略是根据实时测量或者估计网络的当前通信量和拓扑结构做出路由选择[4].动态路由选择策略有：

(1) 独立路由选择策略(HOT POTATO算法).

(2) 集中路由选择策略(RCC操控).

(3) 分布路由选择策略(自由沟通策略).

(4) 混合式路由选择策略.

路由选择在网络设计中是最关键的，采用何种算法进行路由寻址对最终的路径选择有重要的影响.

2改进最小生成树算法在路由选择中的应用

最小生成树算法是在一个有n个节点的无向图G=(V,E)|V|=n中，(u,v)代表连接顶点u与顶点v的边，而w(u,v)代表此边的权重，若存在T为E的子集且为无循环图，使得W(T)最小，则此T为G的最小生成树.最小生成树是原图的极小连通子图，具有保持图连通的最少的边.

最小生成树算法在路由选择中的应用思想是：将源节点与目的节点间的所有节点进行描述，形成路由示意图，如图1所示.首先判断路由图是否为连通图，如果路由图为连通图，则存在一条从源节点到目的节点的多跳直通路由；如果路由图为非连通图，则不存在这样的路由.如果路由图是连通图，则选出最小生成树，从源节点到目的节点在最小生成树上的路径就是选择的路由[5].

图1　路由示意图

在描述路由图中，假设一个参数η为节点到节点间的直通中断概率的门限值，如果当前节点的发射功率pout≤η，则两节点可以直接通信，即一跳通信；如果当前节点的发射功率pout>η，则需要通过中继节点进行多跳通信.图1中SN表示通信的源节点，DN表示通信的目的节点，RN表示通信的中继节点.如果两节点可以一跳直接通信，在图中用实线连接；如果两节点间不可以一跳直通通信，需要多跳，则用虚线连接.实际中图1为有向图，边的权值为通信中断概率，为降低算法的复杂度，将图1简化为无向图，边的权值取有向图中权值最大者.

图2　不考虑多跳次数最小生成树

图3　考虑多跳次数最小生成树

3改进最小生成树算法实现

假设将源节点与目的节点间的所有节点进行描述，形成路由示意图G=(V,E)，V是所有顶点的集合，E是所有边的集合.T=(U,E1)表示最终得到的最小生成树，其中U是V的一个真子集，E1是E的真子集.|V|表示顶点的个数，|E|表示边的个数.将集合V中所有顶点编号V={v1,v2,…,vN},N=|V|，源节点为vk，目的节点为vm，源节点到目的节点的路径为L.

(1) 初始化：令U=φ,E1=φ,E2=φ.

(2)Step1 ：

While(V⊇{vk,vm})

if(|E|<|V|-1)

V=V-{vi}(i=1,2,…,N,i≠k,i≠m),

E=E-{e1,e2,…,ej}

其中,j为vi的度数，e1，e2，…，ej为与节点vi相临的边，跳转至Step1；

Else

图G=(V,E)为连通图|V|=N′,|E|=M′.

(3)Step2：

if(E≠φ)

While(w(ei)=min{w(e1),w(e2),…,w(e|E|)},E1=E1+{ei}无回路)

E1=E1+{ei},E=E-{ei},跳转至Step2；

Else

得到最小生成树T=(U,E1)，vk与vm的路径L；

(4)Step3:

if(E-E1∪E2≠φ)

并且(1-max{w(L),w(e′)})/

(|L|-p+1)>(1-max{w(L)})/|L|)

跳转至Step3；

Else

得到改进后的最小生成树T=(U,E1)，vk与vm改进后的最佳路径L.

(5) 结束.

4改进最小生成树算法仿真与分析

仿真实验结果验证了当实验采用相同的源节点与相同的目的节点，两节点间的距离一致时，改进最小生成树路由选择算法与传统的最小生成树算法对比，可获得更高的信道容量，见图4.

图4　两种路由选择方案下多跳直通

5总结

改进最小生成树算法以高信道容量为目标，在设计方案过程中，即考虑节点间的直通中断概率，又考虑多跳次数对信道容量的影响，先采用克鲁斯卡尔算法得到最小生成树，然后根据多跳次数的影响，通过反复迭带调整最小生成树，直至得到源节点与目的节点间最佳路由.通过实验可以验证：改进最小生成树算法能够获得更高的信道容量.

参考文献：

[1]易平,吴越,邹福泰，等.无线自组织网络和对等网络：原理与安全[M].北京：清华大学出版社,2009：3-18.

[2]张鹏,崔勇.移动自组织网络路由选择算法研究进展[J].计算机科学,2010,37(1):10-22.

[3]RUSS W,DON S,ALVARO R.路由设计的优化[M].北京：人民邮电出版社,2013:413-460.

[4]薛希俊，孙雨耕，刘振肖.基于带宽和跳数的流量工程动态路由选择算法研究[J].电子学报，2002，30(2)：274-278.

[5]陈恒.Ad hoc网络的一种改进路由算法[J].江苏科技信息,2014(21)：24-25.

[6]朱超,洪佩琳,卢汉成,等.空间网络多路径路由算法[J].通信技术，2013，46(9)：42-46.

[7]孙立悦，赵晓晖，虢明.基于中断概率的协作通信中继选择与功率分配算法[J].通信学报，2013，34(10)：84-91.

Application of Improved Minimum Spanning Tree Algorithm in Routing of Mobile Ad Hoc Network

ZHANG Na

(Tieling Normal College, Tieling 112001, China)

Abstract:The improved minimum spanning tree algorithm was proposed for routing,according to the dynamics of mobile ad hoc network and the characteristics of multi-hop network.The proposed scheme takes into consideration both the outage probability among nodes and the effect of hop counts on the channel capacity.By adjusting the minimum spanning tree,the best routing is obtained between source node and destination node.Experimental results show that the improved minimum spanning tree algorithm is able to achieve higher channel capacity.

Key words:improved minimum spanning tree algorithm;mobile ad hoc network;routing

中图分类号：TP393.2

文献标识码：A

doi:10.3969/j.issn.2095-2198.2016.01.016

文章编号：2095-2198(2016)01-0081-05

作者简介：张娜(1982-)，女，辽宁沈阳人，讲师，学士，主要从事计算机应用方面的研究.

收稿日期：2015-09-02