移动Ad Hoc网络中的分布式协作路由算法张晚生;刘凯;王力【摘要】为了提高移动Ad Hoc网络的吞吐量,提出了一种分布式、面向吞吐量优化的协作路由(TOCR)算法.首先分析了协作链路的吞吐量性能,理论分析表明,协作节点可以提高接收信噪比(SNR),从而提高分组的成功接收概率和链路吞吐量；然后在自适应转发分群路由(AFCR)算法的基础上,逐跳选择使得链路吞吐量最大的协作节点来建立协作链路；最终建立从源节点到目的节点具有最大网络吞吐量的协作路由.仿真结果表明,与无协作的路由算法相比,该算法明显改善了网络的吞吐量,尤其是在较低发送功率和大量节点的情况下.%A distributed throughput-optimized cooperative routing (TOCR) algorithm is proposed to improve network throughput in the mobile Ad Hoc network. Through theoretical analysis, by means of a cooperative relay, the received signal-to-noise ratio ( SNR) at a recipient node can be increased, and then the probability of successful packet reception and link throughput are increased. Based on the adaptive forwarding cluster routing (AFCR) algorithm, the TOCR algorithm constructs cooperative links with maximum throughput on a route hop by hop, and finally establishes the route with the maximum throughput from the source node to the destination node. Simulation results show that compared with the noncooperative routing algorithm, the proposed algorithm can obviously improve network throughput, especially in the presence of low transmission power and a large number of nodes.【期刊名称】《西安电子科技大学学报（自然科学版）》【年(卷),期】2011(038)005【总页数】6页(P34-39)【关键词】移动Ad Hoc网络;协作路由;协作通信;节点选择【作者】张晚生;刘凯;王力【作者单位】北京航空航天大学电子信息工程学院,北京100191;北京航空航天大学电子信息工程学院,北京100191;北京航空航天大学电子信息工程学院,北京100191;中国民用航空局飞行校验中心,北京101312【正文语种】中文【中图分类】TN915.04在移动Ad Hoc网络(MANET)中,各节点能够与其他节点通过一跳或多跳进行通信.当两个节点不在彼此的通信范围内时,可以借助其他节点进行中继,从而实现多跳通信.路由算法即是解决源节点或中间节点如何选择下一跳中继节点,直至到目的节点的多跳中继路径的问题,也是影响网络性能的一个重要因素.近年来,协作通信由于可以通过空间分集抵消信号衰落,又比MIMO技术更易实现而受到了广泛的关注.协作通信是指某一个或几个节点协助信息发送节点,将相同信息发送给下一跳节点以达到节约网络能量、增加网络容量、改善信号发送可靠性等性能改善的目的[1].现有协作路由算法大多基于节点发射功率的控制,通过动态调节节点的发射功率来节约节点能量、提高能量效率,从而达到延长网络寿命的目的. Li等人提出一种能量高效的最短协作路径(CSP)算法,该算法以协作通信代价标记各个节点到目的节点的路径权值,利用Dijkstra's算法选择出源节点到目的节点总权值最小的路径[2].文献[3]提出了一种能量高效的时空编码协作路由算法,使在满足一定链路中断概率的情况下,利用分布式或集中式的功率分配方案来降低网络的能量消耗.Hu等人[4]提出了一种基于功率控制的协作机会路由协议(PC-CORP),该协议结合了局部路由、睡眠规律、协作通信和跨层设计的特点,在消耗较低功率的情况下,为网络的通信连接提供较高的鲁棒性和较好的数据传输速率.最小功率协作路由(MPCR)算法[5]首先给出了协作发送链路的能量代价,然后基于最短路径算法通过调节发射端的功率逐跳建立到目的节点的最小功率协作路由.与此不同的是,MPSDF[6]首先在固定功率情况下选择使协作链路误码率最小的中继节点,然后在保证协作链路的误码率低于设定误码率条件下调整发射端的功率,从而实现整个路由的能量消耗最小.文献[7]提出了基于最低能量无协作路径的协作路由算法,其基本思想是首先建立无协作最优路径,然后路径上的前m个节点以协作方式向路径上的下一跳节点发送信息,从而提高了能量效率.文献[8]在此基础上综合考虑了网络层的路由选择和媒质接入控制(MAC)层的多链路竞争避免问题,提出了多流协作路由算法.其中,基于虚链路的虚节点竞争图可以形成吞吐量最大的最优路径,但竞争图的形成需要全局拓扑信息,为此提出了一种分布式协作路由算法,利用两跳范围的局部竞争图代替了理论分析中的全局竞争图.这些算法在节约网络节点能量、提高能量效率方面都能够达到较好的效果,不过在分布式MANET中,节点很难做到根据情况动态调整发射功率.笔者在自适应转发分群路由(AFCR)算法[9]的基础上,提出了一种分布式、面向吞吐量优化的协作路由(TOCR)算法.在节点发射功率一定的情况下,该算法通过协作节点的协作,可以比非协作方式有更高的成功分组发送概率,从而提高了链路吞吐量,改善了从源节点到目的节点间路径的网络吞吐量.仿真结果表明,与AFCR算法相比,TOCR算法在协作节点的协作下明显提高了网络吞吐量.1.1 基本假设网络中每个节点都有惟一的节点身份号(ID)和固定的发射功率.节点间的通信链路是双向的,即如果节点i能收到节点j的分组发送,则节点j也能收到节点i的分组发送.1.2 点对点链路模型点对点链路模型如图1所示,即由发送节点x和接收节点z组成链路(x,z).发送节点x和接收节点z之间的无线信道可以由α和θ描述,θ表示相移因子;α表示增益因子,,其中,d为两节点间的距离,k为路径损耗指数(通常取2～4),hx,z为两节点间的信道系数.对于瑞利衰减信道,其信道增益的概率密度函数为则对于点对点的数据发送方式,接收端z接收到的信号为其中,s(t)为发送信号;功率为PT;n(t)为噪声信号;功率为Pn.1.3 协作链路模型对于协作发送方式,由节点x作为发送端、y作为中继端、z作为接收端组成协作链路(x,y,z),如图2所示.假设接收端z既能收到x发送的数据信号,也能收到y中继的x的数据信号.设各节点的发射功率相同,均为PT,则接收端z收到的信号为2.1 点对点链路的吞吐量分析点对点链路模式下,由式(1)可知,接收端z的输入信噪比为则链路(x,z)的互信息Ix,z为定义链路(x,z)的中断事件为其互信息Ix,z小于频带利用率η0,则链路(x,z)的中断概率为[11]将式(3)、(4)代入式(5),可得则接收端z成功接收分组的概率为定义某跳链路的吞吐量为每秒成功发送的比特数,则此链路的吞吐量为其中,Rb=η0B,为信息发送速率,B为信道带宽.2.2 协作链路的吞吐量分析对于协作通信的数据发送方式,由式(2)可得,接收端的输入信噪比为协作链路(x,y,z)的中断概率为链路(x,z)和(x,y)都中断或链路(x,y)未中断、链路(x,z)和(y,z)都中断的概率,即由于链路(x,z)、(x,y)和(y,z)均为点对点链路,所以式(3)也适用于其他两条链路,将其带入式(10),可得其中,则节点z的分组成功接收概率为协作链路(x,y,z)的吞吐量为由式(8)和式(13)可得,在协作节点的协作下,协作链路的吞吐量比点对点链路的吞吐量有明显提高.TOCR算法以AFCR算法为基础,通过协作节点的帮助,改善了从源节点到目的节点路径上每一跳链路的吞吐量,从而改善了网络吞吐量.3.1 AFCR算法AFCR算法首先采用基于最小节点ID的移动分群算法,将无线网络中的所有节点分成若干个一跳分群,然后再建立、使用和维护路由.该算法包括网络分群、路由建立、路由使用和路由维护4个阶段.(1)网络分群阶段:全网节点首先以任意次序发送一轮控制分组初始化网络,每个节点形成邻居节点表后设置分群计时器,并执行如下算法:①若本节点的ID在其邻节点中最小,则宣布成立新群,群号即为其ID,然后取消计时器计时;否则保持监听至计时终止.②如果节点接收到邻居节点广播的成立新群的消息,则加入该群,同时将此加入消息广播给自己的邻居节点并取消计时器计时;否则,保持监听,直到计时器终止.③在②中,倘若发现邻节点中比自己的ID小的节点都已经宣布加入其他群中,而自己又未被包括在这些群中,则宣布成立新群,同时取消分群计时器计时;否则保持监听,直到计时器终止.④如果节点的分群计时器计时终止,为了确定是加入一个群还是成立一个新群,此节点重置分群计时器,并向未有任何控制消息发送且节点ID比自己小的节点发送群状态询问包,规定收到此包的节点必须作出回应.如果它收到了上述节点的回应包,则继续执行①～③中适合本节点情况的步骤.⑤在步骤④中,如果节点在计时器计时终止前仍无法确定是加入一个群还是成立一个新群,则重新执行步骤④.如果计时器再次终止,则宣布成立新群并将此消息广播给它的邻居节点.(2)路由建立阶段:AFCR算法采用了分布式控制方式来保存路由信息,即每个节点根据接收到的路由信息建立到所有群首的路由.经过分群算法,所有节点被划分为一跳分群,相邻的两个群首之间的路由最多为3跳.因此,每个节点只需广播到群首两跳范围内的节点来建立相邻群群首之间的路由.不相邻群首之间的路由则利用相邻群首之间的路由来建立,最终将通过“源节点—群首—网关节点—…—群首—网关节点—群首—目的节点”的顺序进行路由.(3)路由使用阶段:路由建立过程结束之后,每个节点都保存有1个邻节点表、1个保存了群成员关系的群成员表以及1个保存了到所有群首路由的群首路由表.当节点需要发送或者转发数据分组时,则首先参考邻节点表.如果分组的目的节点是此节点的邻节点,则直接发送;否则查询群成员表中目的节点所属的群首节点.在群首路由表中,如果存在目的节点所属的群首节点的路由项,则向路由项中的下一跳节点发送分组;如果不存在,则缓存在该路由项的队列中,触发查找相关路由,等建立有效的路由时,再发送分组.(4)路由维护阶段:在MANET中,节点的移动或失效等情况会造成通信链路的中断和网络拓扑的变化,将影响网络通信的性能,因此需要对路由进行及时维护.AFCR算法的路由维护工作分为分群保持和路由保持.分群保持就是群首对群成员的加入或退出进行管理,主动或被动地广播相应消息,及时更新群首与群成员关系;路由保持就是当链路中断导致路由失效时,AFCR算法通过链路中断节点的一跳范围内的信息交换来进行局部范围内失效路由的重建.当一跳范围内的路由重建不成功时,它按需逐步扩大失效路由信息交换和路由重建的范围,直至完成路由更新和维护.3.2 协作节点选择算法当分群路由Rc建立之后,Rc上的每个节点x分布式执行TOCR算法(见图3)来建立到下一跳节点z的协作链路.具体执行步骤如下:(1)路由Rc上的每个节点x寻找候选节点y,候选协作节点集合包括所有与节点x和z都能通信的节点.如果候选协作节点集合为空,则本跳链路采用点对点链路模式发送数据.否则执行步骤(2).(2)根据式(13)计算到下一跳节点z对应于候选协作节点y的链路吞吐量SCC.(3)比较计算出的SCC,并得到最大值SCCmax及对应的协作节点y*.(4)重复步骤(1)至(3),直至比较完所有候选协作节点,最后根据选定的协作节点y*建立到下一跳节点的协作链路.在上述步骤的执行过程中,所需的其他节点信息由节点间局部交换的hello分组获得.中继节点选择结束之后,路径上的每个节点都建立了到下一跳节点的协作链路. 综上所述,路径Rc的端到端吞吐量为,其中Rci为Rc上的某跳链路.由于在节点协作情况下路径上每条链路的吞吐量都有明显改善,所以与非协作情况相比,整条路径上的吞吐量也会有明显改善.4.1 仿真环境使用版本为2.29的NS2仿真软件,仿真中网络有N个移动节点,MAC层协议采用IEEE 802.11,天线类型为全向天线,无线传输半径为50 m,移动区域为100 m×100 m的矩形平面区域.初始时节点随机分布于该区域内,构成初始网络拓扑.然后,节点采用Random Waypoint移动模型向在区域内随机选择的某一目标点匀速移动,到达目标点后,构成新的网络拓扑.依此类推,在仿真中考虑这样产生的每个随机网络中所有可能的源节点-目的节点对,取10000个不同网络的平均值作为最终的仿真结果.每个节点的发射功率相同,均为PT=15 dBm,加性高斯白噪声的功率Pn=-70 dBm,路径损耗指数k=4,频谱效率η0=2 bit/(s·Hz-1),信号带宽B=1 MHz.4.2 不同节点发射功率对性能的影响图4表明了不同节点发射功率情况下,TOCR算法和AFCR算法的吞吐量性能比较,网络中节点个数N=30.从图4中可以看出,当节点的发射功率较小时,AFCR算法的吞吐量较小,经过协作节点的帮助,TOCR算法的吞吐量有明显的改善,为20%左右.这是因为经过协作节点的协作,使得接收端的输入信噪比增大,进而使成功接收分组的概率变大,使得吞吐量增大.随着节点发射功率的不断增大,AFCR算法的吞吐量不断增大,而TOCR算法在协作节点的帮助下,在节点发射能量较低时已经具有较高的吞吐量,所以当节点发射功率增大时没有明显的改善.4.3 不同网络节点数对性能的影响不同网络节点数下两种算法的吞吐量性能比较如图5所示.可以看出,当节点的发射功率较小(即PT=15 dBm)时,不同网络节点数情况下,TOCR算法的吞吐量比AFCR 算法的都有明显改善,约为13%.随着网络中节点数的增加,TOCR算法中每跳链路的协作节点选择逐渐趋向于收发两节点间的最佳位置,所以其吞吐量逐渐变大,且变大的趋势逐渐减小.同时,AFCR算法的吞吐量基本保持在1.72 Mb/s,这是由于固定发射功率情况下,路径上群首和网关节点间的分组收发质量不变造成的.4.4 不同频谱效率对性能的影响图6表明了不同频谱效率下各种算法的吞吐量性能比较.设定网络中节点个数N=30,节点的发射功率分别为15 dBm、21 dBm和27 dBm.图7表示了不同频谱效率和3种发射功率条件下,TOCR算法与AFCR算法吞吐量增长率情况.从图6和图7中可以看出,当节点的发射功率较小时,随着频谱效率的增加,TOCR算法的吞吐量增长比AFCR算法的要快,而当节点发射功率较大时,随着频谱效率的增加,虽然TOCR算法的吞吐量增长仍然比AFCR算法的增长快,但两者的增长相差不大.这是因为当节点的发射功率较小时,随着频谱效率的增加,由式(6)可知,AFCR算法的中断概率变大,成功接收分组的概率减小,最终导致其吞吐量的增长率变小.而在TOCR算法中,通过协作节点的协作使得其成功接收分组的概率比AFCR算法的要大,从而使它的吞吐量增长比AFCR算法的要快.上述仿真结果表明:TOCR算法更适合于网络中节点发射功率较低、节点个数较多以及频谱效率相对较高的情况.为了提高MANET的网络性能,笔者研究了协作通信对网络吞吐量性能的影响,并提出了TOCR算法.它在AFCR算法路由建立的基础上,逐跳选择使得链路吞吐量最大的协作节点来建立协作链路,最终建立从源节点到目的节点的协作路由,从而改善了网络的吞吐量.仿真结果表明,与无协作的路由算法相比,TOCR算法在节点发射功率较低、网络中节点数较多情况下,可以有效地提高网络吞吐量.【相关文献】［1］ Zheng L，Tse D N C.Diversity and Multiplexing：a Fundamental Tradeoff in Multiple-antenna Channels［J］.IEEE Trans on Information Theory，2003，49（5)：1073-1096.［2］ Li Fulu，Wu Kui，Andrew L.Energy-efficient Cooperative Routing in Multi-hop Wireless Ad Hoc Networks［C］//Proc IEEE IPCCC 2006.Phoenix，IEEE Press，2006：215-222.［3］ Maham B，Narasimhan R，Hjørungnes A.Energy-efficient Space-time Coded Cooperative Routing in Multihop Wireless Networks［C］//Global Telecommunications Conference.Honolulu：IEEE Press，2009：1-7.［4］ Hu Haifeng，Zhu Qi.Power Control Based Cooperative Opportunistic Routing in Wireless Sensor Networks［J］.Journal of Electronics（China)，2009，26（1)：52-63 ［5］ Ibrahim A S，Han Zhu，Liu K J.Distributed Energy-efficient Cooperative Routing in Wireless Networks［J］.IEEE Trans on Wireless Communications，2008，7（10)：3930-3941.［6］ Sheng Z，Ding Z，Leung K K.Distributed and Power Efficient Routing in Wireless Cooperative Networks［C］//IEEE International Conference on Communications.Dresden：IEEE Press，2009：1-5.［7］ Ehsan K A，Jinane A，Eytan M，et al.Cooperative Routing in Static Wireless Networks［J］.IEEE Trans on Communications，2007，55（11)：2185-2192.［8］ Zhang Jin，Zhang Qian.Cooperative Routing in Multi-Source Multi-DestinationMulti-Hop Wireless Networks［C］//Proc IEEE INFOCOM 2008.Phoenix：IEEE Press，2008：2369-2377.［9］王力，刘凯，刘亭.移动Ad Hoc网络中的自适应转发分群路由协议［J］.北京航空航天大学学报，2009，35（8)：990-995.Wang Li，Liu Kai，Liu Ting.An Adaptive Forwarding Cluster Routing Protocol for Large Scale Wireless Mobile Ad Hoc Networks［J］.Journal of Beijing University of Aeronautics and Astronautics，2009，35（8)：990-995.［10］Proakis J G.Digital Communications［M］.4th Ed.New York：Mcgraw-Hill，2000. ［11］Nicholas L J，Tse D N C，Wornell Gy W.Cooperative Diversity in Wireless Networks：Efficient Protocols and Outage Behavior［J］.IEEE Trans on Information Theory，2004，50（12)：3062-3080.。
