基于混沌映射组播技术的无线移动自组织网络路由研究

郝 平

(陕西工业职业技术学院信息工程学院，陕西 咸阳 712000)

0 引言

随着我国信息化社会的逐步推进，越来越多的社会经济活动采用无线终端部署形式［1］，如在线实时指挥、视频远程管理系统。这些系统主要采取无线移动自组织网的形式进行部署［2］。作为一种组网灵活、抗毁性强的网络体系，无线移动自组织网络能够优化利用资源，充分保障在带宽受限情况下的网络部署于数据分发。另外无线移动自组织网络由于不存在明显的控制中心，因此抗干扰性极强，一旦某个具体的节点因为具体原因而导致不能正常工作时，可以有效地进行节点替换工作［3］。但是，由于节点自由度高，组网过程中的组播协议往往存在巨大的局限性，难以适应实际需求。对此，Zhang Minglong 等人［4］通过引入地址分配机制来改善组播协议，采用动态寻址理念，在小规模无线移动自组织网的实践中取得了成功。不过由于没有引入随机机制，导致大规模部署时组播协议寻址难以有效进行寻址工作;Bettstetter C.等人［5］通过改善组播路由节点的超球体流动机制，采取基于位置的路由算法，使得网络的扩展性大大提高。但是在节点流动性增加的情况下，会导致网络控制开销急速地增加;吕政等人［6］采取虚拟机制，建立了节点/路由的一一对应关系，有效地控制了网络开销。但是由于未能在扩展性上有突破，导致节点的分组投递情况不容乐观。

为了克服上述不足，本文通过引入超球面优良的拓扑特性，采用群论中的直积方法作为组播信号的依据，通过积极映射坐标，实现数据的有效组播，降低了网络的控制开销与能量开销。

1 无线移动自组织网络组播问题与超球面拓扑

在实现无线移动自组织网的分组通信中，任何节点都可以写成是某组的组成部分，可以在一定时间内隶属于这个分组，同时一旦超过了生命周期，就可以离开这个分组［7-9］。为了实现网络拓扑结构的惯例，源节点需要让邻居节点知晓其在网络中的地位，然后某个分组需要周期性地知道该节点详细的拓扑信息，而分组中其他节点将会全部保留该节点的分组信息。因此可以采用超球面拓扑结构［10］来具体描述和表示。

对于一个n 维的超球面而言，其组成节点至少有2n 个［11］。每个节点的具体坐标可以用一串长度为n的向量表示:x=［x1，x2，...，xn］。如果2 个节点x，y处于邻接状态，则它们的组成向量［x1，x2，...，xn］和［y1，y2，...，yn］的有效距离为1。因此采用超球面可以方便地表现源节点的n 种不同的状态，由于超球面的维度是可以无限增加的，因此源节点携带的信息的可扩展性也会大大提高。

网络节点组播信息的超球面拓扑由群Zn×Zn2表示，其中Zn为质数n 的循环群，Zn2 为n 的无限维交换直积。因此元素的组成集合S 由式(1)构成:

其中，s1，s-1，s2，s-2为0，1 组成的二进制随机数。则组播信息发送节点的坐标X 由式(2)决定:

其中，Zn由网络初始状态的n 个节点的状态所决定。

依据模型(2)，定义组播信息生成结构:

根据式(3)～式(6)的超球面的基本解析式，无线移动自组织网络中的任意节点都至少有4 个邻接成员，通过与元素的组成集合S 进行计算，可以得到这4 个邻接成员的解析表达式。而S 中的元素一共可以组成n×2n的排列组合，其中每种组合都有n ×2n+1条邻接向量。显然这些向量对应的顶点和边可以组成哈密尔顿回路。则节点对应的哈密尔顿环的边的解析式f 为:

而任意节点的逆节点的解析表达式f 为:

由于f 和f-正交，且两者之间的元素也是正交关系，因此任意节点与其逆节点同属于哈密尔顿环。

显然，对于任意的n 维长度的源节点而言，与其哈密尔顿环fn都可以通过正交的办法得到与相邻的n×2n个节点的全部消息，而自身的消息也可以有n×2n+1种方式与周围的n×2n个节点相交换。

2 基于混沌映射组播技术的组播算法

由于整个超球面处于同一无线移动自组织网内，因此对于任意节点而言，其状态都是混沌状态，可以将源节点映射为超球面上的几何点，其携带的分组信息由几何点对应的哈密尔顿环及其逆环所决定。每个节点对应的邻接节点至少是4 个，因此整个分组信息由4 层结构所构成:第1 层由根节点构成，主要用来维护分簇信息;第2 层由活动节点构成，主要用来维持网络拓扑结构稳定的开销;第3 层由网络中一般节点所构成，它们和根节点是正交关系;第4 层由邻接节点构成，主要用来进行信息的存储。

由上述群论规则可知:当一个节点发送分组信息时，消息首先在第1 层构成的树中进行分发，依次被2 层、3 层、4 层的节点所感知。当整个消息随着哈密尔顿环返回自身时，整个路由维护过程结束，此时网络拓扑结构处于最稳定的状态。整个算法步骤如下:

Step1 源节点初始化，启动4 层树的构造过程，构造完成转Step2;

Step2 在一层树中，接收到源节点分发信息的节点首先映射为超球面节点，当全部节点接收到信息时，转入Step3;反之，经过一个周期以后，丢弃信息;

Step3 二层树接收到一层树转发的源节点信息后，按照逆环方式将分组信息告知该层次的节点，转Step4;

Step4 当一般节点收到分组信息时，检测自身是否和源节点处于正交状态，当且仅当处于正交状态时，通过环反馈给源节点并转Step5，否则算法结束;

Step5 邻接节点通过收到的信息，将存储有源节点信息的节点进行更新，算法结束。

整个流程如图1 所示。

图1 算法流程图

3 算法仿真

利用OPNET 仿真工具来测试本文路由性能。为了体现所提技术的优异性，将当前性能较好的路由视为对照组:文献［13］中的AODV 算法，并引入平均端到端时延、网络平均负载与分组投递率作为量化质量。具体仿真参数如表1 所示。

表1 仿真参数表

图2 是在网络节点规模大幅度增加的情况下，无线自组织网络中任意2 个节点的平均端到端时延的情况。从图中可以看到，随着网络规模的不断增大，整体上看AODV 算法和本算法的平均端到端时延都会随之提高。但是由于本算法引入了混沌映射机制，通过逆环投递的方式，减少了分组投递中经过的节点数量。因此本算法的平均端到端时延要好于AODV算法。

图2 不同算法的端到端时延

图3 显示了网络节点规模增加的情况下，整个网络开销情况。从图中可以看到，虽然本算法和AODV算法随着网络规模增大，网络控制开销都会随之增大;但是本算法由于节点采用正交方式与周围节点建立联系，大大降低了单次联系过程中的能量开销。因此随着加入网络的自组织节点数量的递增，本算法的优势愈发明显。

图3 网络控制开销测试

图4 显示了随着网络节点移动速度的加快，网络中整体的分组投递率的情况。依图可知，随着网络移动性能的不断提高，网络的拓扑变化速度也随之提高。但是采用本算法网络中的网络投递率始终优于AODV 算法。这是因为由于采用超球面映射的方式，提高了网络节点的混沌度。因此网络节点之间的联系也更加密切，用于控制网络拓扑结构的信息分组数量将大大降低，整个网络分组投递水平也随之提高。

图4 分组投递率对比

4 结束语

随着网络数据及控制难度水平的不断增加，带来了越来越多的网络组播问题。本文基于混沌映射组播技术，采用映射的方式不断对源节点进行正交优化处理，然后通过树状结构实现对全网组播信息的维护，大大降低了平均端到端时延，提高了分组投递率，也降低了终端的网络控制开销水平，对移动互联网的部署具有较强的实际指导意义。

［1］杨林，郑刚.无线多跳网中具有网络编码意识的机会路由协议［J］.清华大学学报(自然科学版)，2010，50(10):1713-1717.

［2］Chi Kaikai，Jiang Xiaohong，Ye Baoliu，et al.Efficient network coding-based loss recovery for reliable multicast in wireless networks［J］.IEICE Transactions on Communication，2014，93(4):971-981.

［3］Kamal A E，Mohandespour M.Network coding-basedprotection［J］.Optical Switching and Networking，2014，11:189-201.

［4］Zhang Minglong，Lu Lu，Liew Soung-Chang.An optimal decoding strategy for physical-layer network coding over multipath fading channels［J］.IEEE Transactions on Vehicular Technology，2015，64(9):4365-4372.

［5］Bettstetter C，Resta G，Santi P.The node distribution of the random waypoint mobility model for wireless Ad Hoc networks［J］.IEEE Transactions on Mobile Computing，2013，2(3):257-269.

［6］吕政，余志军，刘海涛.协作通信中联合信道-网络组播的性能分析与资源分配［J］.西安交通大学学报，2012，46(4):83-87.

［7］Ahlswede R，Cai N，Li S Y R，et al.Network informationflow［J］.IEEE Transactions on Information Theory，2014，46(4):1204-1216.

［8］Zhao Wenrui，Ammar M，Zegura E.Controlling the mobility of multiple data transport ferries in a delay tolerant network［C］// Proc.of IEEE INFOCOM.2005，2:1407-1418.

［9］Altman E，Prakash A，Basar T，et al.Optimal activation and transmission control in delay tolerant networks［C］//Proc.of IEEE INFOCOM.2010:1-5.

［10］El-Azouzi R，Pellegrini F D，Habib B A Sidi，et al.Evolutionary forwarding games in delay tolerant networks［J］.Computer Networks，2013，57(4):1003-1018.

［11］Demmer M，Brewer E，Fall K，et al.Implementing Delay Tolerant Networking［R］.Technical Report，IRB-TR-04-020，Intel Corporation，2014.

［12］Vahdat A，Becker D.EpidemicRouting for Partially Connected Ad Hoc Networks［R］.Technical Report CS-200006，Duke University，2010.

［13］陈敏.OPNET 网络仿真［M］.北京:清华大学出版社，2004.