一种多约束条件的组播路由算法

一种多约束条件的组播路由算法

组播（multiple）是一种点对点通信或两点之间的点对两点信息的传输模式。组播通信方式正成为多媒体通信和分布式计算等应用的基本需求。组播通信在多跳移动无线网络中逐渐地受到重视一般来说,多跳移动无线网络,站点和用户都不固定,没有中央控制节点,节点和节点之间是对等的。它一般工作在异步模式。但是在实际应用中,有一类多跳移动无线网络具有中央控制节点,并且采用TDMA工作模式进行工作。即各个移动用户采用由中央控制节点分配的时隙进行工作。并在这一类多跳移动无线网络中的组播问题不仅仅要考虑利用某一个最小生成树算法使用某一个代价函数构建一个组播树,而且还要考虑组播树的生成与资源消耗的关系。本文就是为了解决该问题而提出的一种组播路由算法。1第1阶段节点状态在有中央控制的情况下,中央节点了解全网的拓扑结构,因此,可将网络形式化为一个带权有向图G=(V,E),这里V表示除中央节点的所有节点集合,E表示连接这些节点的通信链路的集合。|V|和|E|分别表示节点的数量和链路的数量。不失一般性,本文只考虑任意一对有序节点之间最多只有一条链路的有向图。每条链路都有一些相关参数描述链路的当前状态,这些参数统称为链路状态(LinkState),由节点进行维护。每个节点也有一些参数反映节点的当前状态,这些参数称为节点状态(NodeState)。在考虑组播路由中,定义s为源节点,M为所有目的节点的集合,称为组播组,其中每个节点v∈M为一组成员。源节点s产生的分组将被转发到组播组的所有成员M。组播数据流由源节点s经过组播树T=(V2节点的选取约束在考虑的组播路由中,链路代价函数C(e)(即链路权值)主要由:链路的距离或功耗、链路的流量或吞吐量;节点负载等构成。其三个重要的原因为:1)因为节点是运动的,在无线电波可达边界处的节点可能因为运动而使该条链路失效。因此,不能选择距离间隔太远的节点作为中继;2)流量不能集中在几条路由上,造成关键路由出现。所以,不能选择流量过大的链路作为路由;3)不能使某些节点的负载过大,使其称为关键节点。所以,不能选择负载过大的节点作为中继。约束条件主要由最大跳数约束、最小代价树约束和最小性资源消耗约束。最大跳数约束,指从源节点到任意目的节点的路径长度必须低于某个给定的门限值。最小代价树约束,C(T)最小。是指生成的满足最大跳数约束条件的组播树的代价最小。最小性资源消耗约束,指该组播树消耗的资源最小。指生成的组播树在工作时所消耗的时隙资源最少。根据无线网络的特点,某节点一次发射,其周围的邻居节点都能收到信息。如果组播树的中继越少,分配给中继进行数据转发的时隙就越少,资源消耗越少。寻找满足这三个条件的组播树的问题可以定义为在满足跳数限制条件的组播树中寻找满足资源消耗最小且总体代价较低的组播树。3该算法的具体实现3.1基于mph算法的消除算法求出满足跳数约束条件下代价最小的组播树,然后合并该组播树的中继,得到最终的组播树。在求满足跳数约束条件下代价最小的组播树时,以MPH算法作为基础1)求出满足跳数约束条件下代价最小的组播树;2)合并中继,使得到的最终组播树的中继最少。算法假定中央控制节点或源节点了解用于构建组播树的所有网络链路信息,它们可以在网络构建的时候通过某种适合于该网络的算法得到。为描述算法,本文给出几个定义。T表示生成树,用T′来存储节点跳数按升序排序后的生成树。Steiner节点是指组播树中源节点s和目的节点M以外的节点3.2节点位置要求的合并步骤1求满足跳数约束的低代价组播树如下:1)确定是否存在满足跳数约束的组播树。使用Dijkstra最短路径算法排除超过路径长度N的组播组成员,以剩下的组播组成员构建新的组播组M2)初始化:令k=1,从源点s开始,将单节点s作为T3)从M4)将该目的节点和该目的节点到生成树最小路径上所有的Steiner节点一起加入生成树T5)对新加入的节点重复以下过程:按代价值从小到大顺序,考察M6)重复4)、5)直到M步聚2合并中继:定义按照从源到目的节点的跳数大小对T进行分级,把处在第i跳的中继节点和目的节点称为第i级节点T(i),T(i)⊂T。∀∃k∈T(i)。假定A(k)是k的下一级T(i+1)中与其直接相连的节点形成的集合;N(k)是与k相邻且满足链路代价门限的节点的集合。合并的原则为1)排除T(i)中的节点度为1的节点,并重新存储为T′(i);2)求出T′(i)中的每个节点v的A(v)和N(v);3)判断A(v)I(UN(T′(i)-v))=A(v)是否成立;4)如果成立,那么把A(v)中的节点分别连入到T′(i)中该节点所对应的那个邻节点上。同时对节点v作两方面处理:(1)如果节点v不是目的节点,那么删除v;如果是目的节点,则保留v。(2)如果不成立,那么保留v。合并过程为:1)按照跳数大小对T进行分级处理,并对同一级的目的和中继节点进行存储;2)从最大跳数的那一组目的节点的上一级存储节点按照合并原则进行合并,合并完成则到更上一级进行合并处理;3)合并进程一直到源节点的下一级结束。合并后的组播树为所求得的组播树。3.3中性化的组播树合并定理如果存在满足跳数约束和最小资源消耗约束的组播树,那么该算法就能够构建满足这两个约束条件的低代价组播树。证明算法步骤1中的1)首先判断源与所有目的节点之间的最大跳数是否满足跳数限制。如果不满足,显然不存在满足跳数限制的组播树。那么也不存在资源消耗问题,所以满足这两个条件的低代价组播树也不存在。如果存在某一部分目的节点满足跳数限制条件,那么排除不满足条件的目的节点,以剩下的节点作为组播组M式中C对形成的组播树按步骤2进行中继合并,根据合并原则3),该合并过程只对处在某一级的某一类中继节点进行合并。该类中继节点的特点是其中继的下一级节点都是该级中继的其他中继节点的满足给定链路门限的邻节点。故合并的结果是,这一类中继节点的下一级节点都连接到其他的处在同一级的中继节点上,该类中继节点被删除,如果是目的节点则保留。删除一个中继节点,则减少为该中继节点分配一次时隙,那么资源消耗减小。经过合并