基于最优子集的MPR选择算法研究.pdf

《基于最优子集的MPR选择算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第203145卷年第6月2期成都大学学报(自然科学版)V_o1．34No．2JournalofChengduUniversity(NaturalScienceEdition)Jun．2015文章编号：1004—5422(2015)02—0156—04基于最优子集的MPR选择算法研究张洪，一，王传真，陈海霞，叶雪，罗阳(1．成都大学计算机学院，四川成都610106；2．成都大学模式识别与智能信息处理四川省高校重点实验室，四川成都610106)摘要：通过对AdHoc网络中最优链路状态路由(OptimizedLinkStateRouting，OLSR)协议的研究

2、，从数学集合的角度来分析Ⅷ，R(舢iPointRelay，MPR)集选择问题，通过将一跳邻居节点及其所连接的一条邻居节点抽象化为包含子集的集合，计算剩余集合的独立子集生成MPR中继节点，从而找到节点数量最少的MPR集．仿真实验结果表明，该算法降低了网络传输的延时，提高了网络传输的速度．关键词：AdHoe；OLSR；集合；路径选择中图分类号：．5；TP301．6文献标志码：A这样做减小了控制分组的洪泛范围．因为任一节点0引言仅选择部分邻节点作为它的中继节点，而也只有中AdHoc网是一种多跳的、无中心的自组织无线继节点才能转发和控制分组，其余邻节点只处理收网络

3、，又称为多跳网(Multi—hopNetwork)或自组织网到的分组信息而不转发，所有被选中转发和控制分(Self-organizingNetwork)uj．整个网络没有固定的基组的邻节点被称为中继节点MPRS．础设施，每个节点都是移动的，并且都能以任意方式2)缩减控制分组的大小．节点并不发布与所有动态地保持与其他节点的联系．OLSR_2协议是一个相邻节点的链路状态信息，而是只发送与它相邻重要的MANET路由协议，而支撑此协议的关键技MPR点之间的链路状态信息．术在于MPR．对此，张信明等通过采用不同遗传2传统OLSR的局限性策略将此遗传算法衍生成了4个序

4、列算法，并在随机生成的拓扑上对其进行模拟，取得了一些成果，但2．1传统MPR选择该遗传算法的编程实现比较复杂；钟珞等[4将蚁群传统的OR路由协议采用2种方法来减少由优化用于最小MPR集选取问题的求解，给出了一种于链路状态信息洪泛所带来的路由开销．第一种方基于候选解的改进蚁群算法CSACO，但由于蚁群算法是采用多点中继，每个节点在自己的一跳邻居节法利用信息的正反馈特点，容易使结果陷入局部最点中选择一部分节点作为自己的MPR，由MPR而不优解．在此基础上，本研究提出了一种改进方案，以是所有的一跳邻居节点转发链路状态消息，通过此寻找最小MPR集，并通过仿真验证了

5、改进方案的MPR实现路由控制消息的选择性洪泛；第二种方法有效性．是链路状态信息的压缩]，链路状态信息只是描述MPR选择节点(MPRSelector)与MPR之间的链路，1OLSR特点而不是与所有的一跳邻居节点的链路．而在选择OLSR是一种先应式链路状态路由协议，主要应MPR时，经典的OLSR路由协议采用以连接度为参用于MANET网络_5]，并根据MANET的要求在传统考标准的算法．的LS(LinkState)协议的基础上进行优化，其关键在2．2传统MPR选择的问题于多点转播(MultiPointRelays，MPRS)．它对于传统由于传统OLSR路由协议只

6、计算跳数最短路的LS协议做出的优化有：径，而且路由协议只是尽力而为地传输数据分组，没1)仅选择部分节点作为中继节点来控制分组，有考虑网络中间节点的拥塞情况和无线链路的实际收稿日期：2015—03—18．基金项目：四川省教育厅自然科学基金(14ZB0368)、成都大学校科技发展基金(2012XJZ19)资助项目作者简介：张洪(1980一)，男，硕士，讲师，从事计算机网络结构研究．第2期张洪，等：基于最优子集的MPR选择算法研究·157·状态，所以选择的MPR集不一定是最小的．因此，传统OLSR路由协议已经无法满足移动AdHoc网络提供更高质量和更多种类业务的

7、要求．3MPR选择的改进3．1传统选择产生的问题传统MPR选择节点如图1所示，具体步骤如下：1)选取唯一的二跳邻居，将其所在的一跳邻居图3集合划分示意图所包含的所有二跳从整个二跳邻居中去除，得到MPR节点集合{e，f}I大连接度的一跳邻居作为MPR，而本方法将继续沿2)对剩下的二跳邻居进行最大连接度选择直至二用寻找唯一的方法进行下去直至二跳邻居SEC{1，跳邻居为空，最终得到的MPR节点集合{e，f，b，C，a}．2，3，⋯，n}为空．显然，进行完第一次MPR节点的选取后所剩下的二跳邻居点，没有一个二跳邻居是唯一属于一跳国节点A邻居的．图4为第一次选择后的

8、结果．●MPR节点国普通一跳邻居0：：：跳邻居一连接囤1传统MPR