无线传感网络中QoS约束多播路由算法＊

伍新华

（武汉理工大学计算机学院 武汉 430063）

QoS多播路由技术的目标是找到一种算法或策略，在给定的网络和多播需求的情况下，寻求一种链路连接方式，使网络资源能够得到有效利用［1］.文献［2］中将基于图论的最小能量广播／多播问题归纳为最小能量广播树和最小能量多播树问题，文献［3］中提出最大剩余能量的QoS多播路由算法，文献［4］提出了基于平衡节点能量消耗的思想，通过平衡节点能量的消耗或减少能量低的节点参与路由的几率来提高网络的寿命.本文讨论了延时、带宽及节点剩余能量的问题，提出了一种多QoS约束的能量有效多播路由算法（EMRA）.

1 网络模型

定义2 如果p（s，t）满足（d（s，＊）＋d（k，t）≤ Dmax）∧ （b（i，j）≥ Bmin）∧ （R（P（s，t））＝min［r1，…，rf］，则满足此约束的路径为能量消费最小路径；满足带宽和时延约束的最小能量路径多播树问题是一个NP完全问题［5］，可以采用一些启发式算法加以解决.

2 EMRA

2.1 EMRA节点选择策略

多播节点的加入操作涉及到加入点的选择问题，一般有随机点策略、最小时延点和能量消耗最小三种选择策略.随机点策略就是从多播子树中任选一个路由节点作为多播终点的加入点.最小时延点策略是s到d的最小时延路由路径与多播子树的交点作为多播终点d的加入点.最小能量点策略则是选择从s到d的能量消耗最小路由路径与多播子树的交点作为多播终点d的加入点.仿真实验结果表明，最小能量消耗策略费用精度最好，所以，EMRA选择最小能量点策略.

2.2 EMRA实现

EMRA基本思想是利用可行链路来构建满足带宽和延时约束的最小能量消耗的多播路由树，因此利用文献［6］中的BIP最小生成树的Prim算法的基本思想来构成.以源节点s为根节点，首先找到一个能量耗费最小的节点添加到树中，然后BIP使用最小能量增量的原则每次往树中添加一个节点，直到所有的节点全部加入到树中，最后得到的树即是一个最小能量多播树的解.

EMRA首先选择多播信源构成初始多播树，然后根据多播成员的连接请求或退出请求，依照加入和退出操作规则，动态地建立或切断连接，多播树的形成过程就是多播成员的动态加入和退出过程.在EMRA的形成过程中，路由器或节点需在其路由表保存一些特定的信息.为了描述方便，定义EMRA的主要消息如下：Request（加入请求消息），节点t向多播信源s发送请求加入多播；Accept（加入确认消息），源节点s向请求授权点t发送确认加入请求；Delete（链路删除消息），节点t沿多播树向父节点w逆向发送请求删除链路（w，t）；Establish（建立状态），路由资源在该节点已分配完毕.

EMRA是以分布的方式来建立多播树的，每个节点以同样的算法，四种不同的节点（源节点、树节点、中间节点和目标节点）在协议中以不同的方式交换信息，每个节点的操作由到达的控制消息所触发（Request，Accept，Delete，Establish）.链路e的带宽、延时和能量分别为B（e），D（e），R（e）；而r＿table为局部路由表；对于任何节点v，r＿table［v］.b为在最短路径上的有用的带宽；r＿table［v］.d为在最短路径上的有用的延时；r＿table［v］.r为在最短路径上的有用的能量.EMRA步骤如下.

步骤1 初始化，删除所有带宽大小于Bmin约束的链路.

步骤2 多播源节点s广播Request请求报文，开始链路的查找.

制造任务分解的主要目的是为了获得一定粒度的子制造任务，实现生产过程的均衡和制造服务的合理匹配。制造任务分解的基本过程如下：

步骤3 当某节点i接收到Request后，如果已经接收并处理过该Request，则向其相邻节点转发；否则，如果delay（p（u，v））＞Dmax，则指针poi［u］指向节点u的父节点.

步骤4 计算能量最小路径 如路径满足能量最小定义2，则poi［y］＝x；如x的状态为Establish，则计算d（P（s，x））；如delay（P（s，x））≤Dmax，则 While poi［u］NIL，发出加入请求消息Request.

步骤5 如果某节点k接收到节点j发送的Accept消息，如果链路e（j，k）状态为Establish.

步骤6 检查多播目的节点是否全部加入多播树T（s，M），如果没有，则源节点s继续广播Request报文，转步骤2，否则执行步骤7.

步骤7 执行剪枝算法，利用后序遍历算法以多播源节点s为根节点遍历以上生成的多播树，并且在访问某叶节点时，如果该叶子节点是一个非多播节点，则删除该节点，直到多播树中所有叶子节点均为多播目的节点.

3 EMRA正确性证明与复杂性分析

3.1 EMRA正确性证明

定理1 EMRA所构造的多播树T（s，M）定能满足带宽、延时、最小能量约束.

证明 （1）EMRA是根据定义2来计算能量最小路径；（2）在EMRA中，当且仅当d（P（s，v））≤Dmax和b（P（s，v））≥Bmin），才发出加入请求消息，所以，对于∀P（s，v）⊆T（s，M），有P（s，v）定能满足延时和带宽约束.

结合证明（1）和（2）知，EMRA所构造的多播树T（s，M）定能满足带宽、延时和能量约束，证毕.

定理2 EMRA搜索的最小能量路径是无环的.

证明 首先，增加第一个目标节点到树上的过程中没有产生环路.设当前要增加到树中的节点为vd∈V，则增加vd到树上（当前只有一个多播源节点s）的过程即为寻找路径P（vs，vd）使之能量增加最小的过程.在EMRA的执行过程中，选择满足定义1的方式构造，同时每条最小能量路径都是以源节点s为起始节点加入的.在r＿table路由表中只存在一个输入和一个或多个输出接口，所搜索到的路径形成的是一种树结构.在新节点加入后，组内各节点间仍构成一棵多播树，故TsM 必是无环的树型结构.其次，假设已构造部分没有环路，新增加节点的过程产生环路［6］.

采用反证法，如图1所示，使用实线表示已经构造的多播树，虚线表示即将加入到多播树上的部分.如果P（v8，v10）是EMRA选择路径存在的环路，则必有P（vt，v10）包含多播树上的某个节点，不妨设为v9；由于P（v8，v10）是v10与树上所有节点S＝｛v1，v2，v3，v4，v5，v6，v7，v8，…｝中所有路径中满足带宽和延时约束的最小能量路径，则有路径P（v8，v10）的能量代价必小于 P（v9，v10）；而路径P（v8，v10）包含节点v9，则路径P（v8，v10）的能量就等于路径P（v8，v9）的能量加上路径P（v9，v10）的能量之和，显然两者相互矛盾，原假设不能成立.即新增节点过程中没有产生环路，所以EMRA在多播树的产生过程中是无环路的.

图1 EMRA的无环路径

3.2 EMRA复杂性分析

定理3 EMRA的消息的复杂度为O（｜M｜｜E｜），计算复杂度为O（｜n｜2）［7］.

证明 EMRA的复杂度可根据生成多播树的计算复杂度和所需的报文数来进行分析；前者主要涉及到摸索路径和多播生成树所需要的开销，后者主要根据生成多播树的报文交换功能所需要的计算开销.在EMRA中，路径计算一般在端点进行，根据QoS需要计算新节点加入多播树的路径.而EMRA的计算复杂度由加入请求、加入和退出等操作部分组成.加入请求操作消息的复杂度最多为O（｜E｜），M 个多播节点加入操作消息的复杂度最多为O（｜M｜｜E｜）；退出操作的退出请求消息的复杂度最多为O（｜E｜），删除请求和删除操作消息的复杂度都为O（1），故EMRA消息的复杂度由加入操作消息的复杂度决定，即为O（｜M｜｜E｜）.

同时在EMRA中，每个节点实际表示一个路由器，算法在每个路由器上进行.算法将每个目的节点加入到树中所需的控制信息算作一次信息传递，而不考虑中间节点的信息传递.如果没有回路产生的情况下，就有连接n个目标需要从源节点或分支节点发送n个Request加入请求消息到目标节点，至多n－1次信息从n－1个目的节点发出.EMRA在最坏情况下需要2n＋k 次信息传递，这时最坏情况为每次在加入一个目的节点时，k＝（n－2）＋（n－3）＋…＋1＝（n－2）×（n－3）／2，因此，EMRA共需要O（n2）次信息传递，如果每次信息传递用一个单位时间，这时EMRA的收敛时间就为O（n2）.

4 仿真与结果讨论

网络仿真平台为NS2，实验中的网络图由Waxman随机图模型生成，对 EMRA，BIP［8］和MEMT算法进行了仿真实验中.每次实验中，随机选择多播源节点和若干个请求点，每种类型的实验重复100次，取各次结果的平均值，以保证结果的可信度.

图2表示多播树的能量消耗随多播节点数增加的变化曲线.在该仿真实验中网络节点数被设为500，时延为300.当多播节点数增加时，对EMRA，BIP和MEMT算法所产生的能量消耗也增加，但EMRA增加程度较小，相同多播组EMRA的能量消耗较小.由于控制报文长度增大，其能耗也会相应增加.因此，在网络规模较小的情景下路由控制报文带来的额外能耗抵消了能控机制节省的能量，然而随着网络节点数目的增多，EMRA其能耗将大大低于BIP和MEMT算法.

图2 3种算法的多播树能量消耗

图3给出了EMRA，BIP和MEMT算法路由请求平均成功率的随时延约束变化时的曲线.从图中可以看出，EMRA的路由请求平均成功率高于BIP和MEMT算法.

图3 3种算法路由请求平均成功率

图4显示了在时延限制Δ＝1008060时，网络节点数在［50，500］间变化时，EMRA的平均消息数.可以看出，随着节点数的增加，EMRA的平均消息数增加很慢，不会产生消息风暴，这表明EMRA可以在大型网络中应用.

图4 EMRA的平均消息数变化

通过对EMRA，BIP和MEMT三种算法的仿真结果进行比较发现，EMRA在性能上较优越于其它两种算法，能很好地满足多QoS约束的无线传感网络的实时应用需要.

5 结束语

EMRA在实验中反映无线网络真实特性的带宽、剩余能量和延时等重要因素，同时通过可行链路的定义使生成的多播链路满足QoS约束，这样有效地减少了生成多播树的开销.仿真实验结果表明EMRA为多QoS约束的无线传感网络多播路由技术提供了一种新的有效途径，能适用于各种网络规模和群组规模，可扩展性良好，具有较好的应用前景.

［1］李腊元，李春林.动态QoS多播路由协议［J］.电子学报，2003，9（9）：1345－1352.

［2］Ioannis C，Panagiotisk C.Energy－efficient wireless network design：lecture notes in computer science（ISAAC03），LNCS 2906［C］／／Berlin：Springer－Verlag，2003：585－594.

［3］Younism A.An energy－aware Qos routing protocol for wireless sensor networks［C］／／Proceedings of the 23rd International Conference on Distributed Computer Systems Workshops Los Alamitos USA IEEEE Computer Society，2003：710－715.

［4］Cheng M X，Sun Jianhua，Min Mank，et al.Energyefficient broadcast and multicast routing in Ad Hoc wireless networks［C］／／Proceedings of the 2003 IEEE International，2003：87－94.

［5］Mario Z，Hubaux J P，Christian E.Minimum－energy broadcast in all－wireless networks：NP－completeness and distribution issues：proceedings of the 8th annual international conference on mobile computing and networking（MOBICOM）［C］／／Atlanta，Georgia：ACM Press，2002：172－182.

［6］孔令山，丁 炜.一种多约束QoS多播路由算法［J］.通信学报，2003，24（7）：30－36.

［7］许 毅，李腊元.一种支持多QoS约束的多播路由协议［J］，小型微型计算机系统，2005，26（12）：2065－2068.

［8］Kim Y，Li S.Timescale of interest in traffic measurement for link bandwidth allocation design［C］／／Proceedings of IEEE INFOCOM：1996.