２０１２年第６期　福建电脑　４５　

基于随机网络编码的ｏｄｍｒｐ协议研究　

焦进　（河南科技大学管理学院河南洛阳４７１０２３）　

【摘　要】：ＯＤＭＲＰ协议是基于ｍｅｓｈ网络的Ａｄ　ｈｏｃ多播路由协议，可提供较好的性能，　但在路由过程中需在网络中进行洪泛，这极大的降低了网络的性能。本文首先分析了ＯＤＭＲＰ　的机制。指出其有待改进的地方。之后采用随即网络编码对ＯＤＭＲ．Ｐ协议进行改进，提出了基于　网络编码的ＮＣ—ＯＤＭＲＰ协议。　【关键词】：Ａｄ　ｈｏｃ；多播路由；ＯＤＭＲＰ；网络编码　０、引言　Ａｄ　ｈｏｃ网络是一种分布式的多跳网络系统．　该网络中不需要中心节点。具有自组织、自愈的能　力。当前Ａｄ　ｈｏｅ多播协议主要有两大类型：基于　树形拓扑（ｔｒｅｅ）的协议（比如ＭＡＤＯＶ）和基于网　格拓扑（ｍｅｓｈ）的协议（比如ＯＤＭＲＰ）。学术界普遍　认为基于网格的多播协议性能更好【１】．因此对于　ＯＤＭＲＰ协议的研究具有重要意义。　１、ＯＤＭＲＰ协议路由机制　ＯＤＭＲＰ（Ｏｎ－Ｄｅｍａｎｄ．Ｍｕｌｔｉｃａｓｔ　Ｒｏｕｔｉｎｇ　Ｐｒｏｔｏ－　ｃｏ１）是一种按照信源的需求建立并维护组成员和　多跳路由的基于ｍｅｓｈ的路由协议。它包括路由请　求阶段和应答阶段。它使用了转发组的概念来建　立多播路由．并通过”软状态”的方法来维护多播　组的成员．节点要脱离多播组时不需要明确的控　制报文。　当信源需要路由时．先广播一个Ｊｏｉｎ　Ｑｕｅｒｙ　包。当一个节点收到了一个Ｊｏｉｎ　Ｑｕｅｒｙ包后．把该　包的源地址和ＩＤ加入自己的消息缓冲区（Ｍｅｓ．　ｓａｇｅ　Ｃａｅｈｅ）￣来鉴别是否已收到过该包。若没有　收到过则将包加入消息缓冲并重新广播该包。当　加入请求包到达多播接收节点时．接收节点产生　一个Ｊｏｉｎ　Ｒｅｐｌｙ包并广播给其邻节点。节点收到　Ｊｏｉｎ　Ｒｅｐｌｙ包后，检查自己是否是包的下一跳。若　是，则节点把自己置转发组成员。产生新的Ｊｏｉｎ　Ｒｅｐｌｙ包并广播。每个转发组成员产生并发送自己　的加入应答包直到到达信源节点。这样从信源到　接收者的路径就建立起来了　２、基于随即网络编码的ＯＤＭＲＰ协议　ＯＤＭＲＰ协议能够提供较好的性能．但它在　建立多播组时采用洪泛的方式．极大地浪费了带　宽和增加了路由的控制开销。因此，逼着对　ＯＤＭｆｕＰ协议进行了改进．提出了基于网络编码的　ＯＤＭＲＰ协议——ＮＣ—ＯＤＭＲＰ（Ｎｅｔｗｏｒｋ　Ｃｏｄｉｎｇ—　ＯＤＭＲＰ）．有效地降低了网络通信的开销。　２．１随机网络编码概述　通过研究人们发现在多播网络中．通常采用　的的把多播信息看做是一个仅仅能被路由和复制　的“流体”的做法并不是最优的．可以通过网络编　码的方法对传统多播进行改进．极大地节约带宽。　提高网络流量。中继节点从输入链路获得信息，对　接收到的符合编码条件的多个信息进行编码得到　＿二个编码后的信息．再把经过编码后的信息发送　到输出链路［２１．这样既可有效地节约了网络带宽．　增大网络吞吐量。之后Ｈｏ，Ｍｅｄａｒｄ等人提出了随　机网络编码［３１．它的提出将网络编码拓展到了无线　网络并不再局限于确定的网络拓扑结构。　２．２随机网络编码算法　线性网络编码能够有效地构造编码向量．确　保信宿节点成功译码．但它使用的是集中式算法。　需对整个网络的拓扑结构有全面的了解　因此线　性网络编码算法对并不适用于拓扑结构动态变化　或规模较大的网络。随机网络编码算法较好的解　决了这个问题．这种算法采用随机选择编码向量　的策略：对于除了信宿节点外的所有中间节点．只　要在一个足够大的有限域Ｆｑ上随机选择它们输　入链路到输出链路的映射．而且各节点映射关系　的选取是相互独立的．就能以较高概率使各个信　宿节点对应的系统转移矩阵Ｍｔ满秩．即各信宿节　点能以较高的概率成功译码。设Ｇ：ｆＶ，Ｅ）表示无　环有向图．其中Ｖ是顶点集．Ｅ＝Ｖ　ｘ　Ｖ是边集且各　边均为单位容量。Ｓ∈Ｖ为信源节点（发送节点），

　福建　电脑　２０１２年第６期　Ｔ∈Ｖ为信宿节点集（接收节点集）。网络的最大流　为ｈ。信源节点将原始信息分成ｈ个向量ｘ１。…　ｘｈ，中继节点进行编码操作：ｙ＝ｇｌｘ１＋ｇ２ｘ２＋…＋　，　ｇ＝（ｇ　一，　是全局编码向量，初值为ｈ维单位向　量，是和编码后的信息向量ｙ一起传输，记为（ｇ，　ｖ）。中继节点随机的在有限域ＧＦ（ｑ）生成ｈ维局部　编码向量对收到的ｈ个（ｇ，ｙ）进行线性编码，得到　一个编码后的（ｇ，Ｙ），再发送给邻节点。当信宿节　点收到ｈ个线性无关的（ｇ，Ｙ）后，则根据高斯消　元法即可解码　由此可见是否能够解码取决于在　有限域ＧＦ（ｑ）上随机选取的局部编码向量必须线　性无关。理论上可证明：当符号域大小为ｑ＝２１６　时．任何接收节点均可以至少以概率９９．６％成功　译码［３１．文献　指出，在实际应用环境中，符号域的　大小为ｑ＝２ｓ就足够了，这极大的降低了网络节　点译码的开销　２－３　ＮＣ—ＯＤＭＲＰ协议　ＮＣ—ＯＤＭＲＰ协议的基本思想即通过对　ＯＤＭＲＰ协议的ＪｏｉｎＱｕｅｒｙ和Ｊｏｉｎ　Ｒｅｐｌｙ包进行扩　展．实现在ＯＤＭＲＰ协议建立路由阶段，采用网络　编码算法来代替简单的洪泛。从而减少带宽的浪　费、降低协议开销的目的。并且无需改变ＯＤＭＲＰ　协议的流程．仅在节点处理报文时采用线性随机　网络编码算法，加入编码解码步骤即可实现。ＮＣ—　ＯＤＭＲＰ协议的报文格式如下：　ＮＣ－ＯＤＭＲＰ报头　＋＿原ＯＤＭＲＰ报文—＋　

Ｔｙｐｅ：ＮＣ—ＯＤＭＲＰ协议报文的类型。分别为　ＮＣ—ＯＤＭＲＰ的Ｊｏｉｎ　Ｑｕｅｒｙ和Ｊｏｉｎ　Ｒｅｐｌｙ报文。　Ｏｆｆｓｅｔ：包头的大小。　Ｐｒｅｖｈｏｐ：上一跳节点地址。　Ｄａｄｄｒ：目的节点地址，即多播组地址。　ＮｏＰ：参与编码的报文数量计数　Ｖｅｃｔｏｒ：随机编码向量．未编码报文该项为　空。　Ｐａｃｋｅｔ　ＩＤ　ｌｉｓｔ：报文中参加编码的报文标识　（Ｐａｃｋｅｔ　ＩＤ）列表　ＯＤＭＲＰ：ＮＣ—ＯＤＭＲＰ封装的原ＯＤＭＲＰ报　文。　．　３、结束语　Ａｄ　ｈｏｃ的研究和应用是当前学术界的热点　ａｄ　ｈｏｃ路由协议在建立路由时普遍采用洪泛的方　式．这样极大地占用了网络带宽．增加了路由的控　制开销，浪费了ａｄ　ｈｏｃ节点有限的能量。网络编　码算法的出现为解决这一问题提供了较好的方　法。本文针对ＯＤＭＲＰ协议的缺点进行了改进。将　ＯＤＭＲＰ和网络编码结合起来．提出了ＮＣ—ＯＤＭ．　ｆｕＰ协议，可有效地降低路由时节点的转发次数．　从而减少带宽的占用和路由控制开销．降低了节　点能量的消耗．对ａｄ　ｈｏｃ路由协议的研究进行了　一次有益的尝试　

参考文献：　［１】Ｔｈｏｍａｓ　Ｋｕｎｚ　ａｎｄ　Ｅｄ　Ｃｈｅｎｇ．Ｏｎ—ｄｅｍａｎｄ　ｍｕｌｔｉｃａｓｔｉｎｇ　ｉｎ　ａｄ—ｈｏｃ　ｎｅｔｗｏｒｋｓ：ｃｏｍｐａｒｉｎｇ　ＡＯＤＶ　ａｎｄ　ＯＤＭｔ￣．Ｐｒｏ—　ｃｅｅｄｉｎｇｓ　ｏｆ　２２ｎｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕｔｉｎｇ　Ｓｙｓｔｅｍｓ，２００２：４５３—４５４　［２１　Ｔａｋｕ　Ｎｏｇｕｃｈｉ，Ｔａｋａｈｉｒｏ　Ｍａｔｓｕｄａ，Ｍｉｋｉ　Ｙａｍａｍｏｔｏ．　Ｐｅｄｂｎｍｎｃｅ　Ｅｖａｌｕａｔｉｏｎ　ｏｆ　Ｎｅｗ　Ｍｕｌｔｉｃａｓｔ　ＡｒｃｈｉｔｅｃｔｕｒｅⅥ，ｉｔｌｌ　Ｎｅｔｗｏｒｋ　Ｃｏｄｉｎｇ［Ａ］．ＩＥＩＣＥ　Ｔｒａｍ．ｃｏｍｍ［Ｃ］，２００３，Ｅ８６一Ｂ　（０６）：１７８８—１７９５．　【３】Ｈｏ　Ｔ，Ｍｅｄａｒｄ　Ｍ，Ｓｈｉ　Ｊ．Ｏｎ　Ｒａｎｄｏｍｉｚｅｄ　Ｎｅｔｗｏｒｋ　Ｃｏｄｉｎｇ［Ａ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　４１ｓｔ　Ａｎｎｕａｌ　Ａｌｌｃ￣ｏｎ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ　Ｃｏｎｔｒｏｌ　ａｎｄ　Ｃｏｍｐｕｔｉｎｇ【Ｃ】，２００３，Ｐａｇｅｓ：　４４２－４４５．　【４】Ｐｈｉｌｉｐ　Ａ．Ｃｈｏｕ，Ｙｕｎｎａｎ　Ｗｕ，Ｋａｍａｌ　Ｊａｉｎ．Ｐｍｃｔｉｃａｌ　Ｎｅｔ－　ｗｏｒｋ　Ｃｏｄｉｎｇ［Ａ］．Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　４１ｓｔ　Ａｎｎｕａｌ　Ａｌｌｅｒｔｏｎ　Ｃｏｎ－　ｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｃｏｎｔｒｏｌ　ａｎｄ　Ｃｏｍｐｕｔｉｎｇ，２００３　

（上接第３４页）　不断地探索和总结，不断完善分级教学，才能取得　更好的教学效果。　

参考文献：　【１】张灿龙，张超英，张兰芳．师范院校《大学计算机基础》分　级教学改革初探Ⅱ】．高教论　坛，２００９，（４）：３３—３５．　［２１向伟．大学计算机基础分层教学模式的实践研究Ｕ】．四　川文理学院学报，２０１０，２０（２）：１　１９－１２１．　【３】代秀娟．大学计算机基础分级教学的问题及对策Ｕ】．代　秀娟，２００９，（１）：２２４－２２０．