一种基于两测度的无线链路重要性评价方法

董志远，张 品，陈 磊

(杭州电子科技大学通信学院，浙江杭州310018)

0 引言

在无线网络的设计和维护过程中，网络的可靠性是一项重要指标。链路失效，轻则可以引起通信网络性能的下降，重则可能造成网络的局部瘫痪，故在国内外，对无线网络中链路的重要性进行评价，对研究通信网络的可靠性有着重要的意义［1～5］。而往往各种算法对网络中存在的串联链路视为等重要性，但现实中的网络往往为非对称网络，各条串接链路之间也不是对称的关系，故将某些串联链路的重要性视为相等是不妥当的。因此，当串联链路上多条链路发生故障时，应如何考虑确定维修的先后顺序，使网络遭受的损失最小，以提高网络的可靠性。文献1提出了一种基于生成树数目的重要性评价方法，定义最重要的链路删除后，图的生成树数目最少，则这条边最重要，是一种可靠的评价方法。本文在链路删除法的基础上，提出一个基于两种测度的链路重要性评价方法，该方法不仅可以评价每条链路的重要性，同时还能够区分那些在网络中处于串联的链路的重要性，在不改变链路重要性的趋势的基础上评价串联链路的重要性，与链路删除法相比具有更高的精确度。

1 网络模型与理论基础

1.1 网络模型

无线网络可以用图G=(V，E)来表示，设G为有n个节点和m条边的无自环无向连通图。V={v1，v2，…，vn－1，vn}代表顶点的合集，图的顶点对应网络中的节点，E={e1，e2，…，en－1，en}代表边的集合，图的边对应网络中的链路。假设无线网的拓扑结构固定不变，节点之间不能够相互备份;所有节点的损坏概率相同，均为p(0＜p＜1);网络中的节点只有两种状态:正常工作和失效，且每个节点的故障发生是相互独立的，通信链路不会发生故障。

G的全顶点完全关联矩阵Ac=［aij］由n行和m列组成，每一行表示一个顶点，每一列表示一条链路。当G是有向图时，完全关联矩阵Ac中的元素aij定义如下:

1.2 理论基础

Kirchhoff矩阵，对于无向图G，假设它的完全关联矩阵为B，则其Kirchhoff矩阵为BBT。

MatrixTree定理，设G为无向连通图，G的所有不同的生成树的个数等于其Kirchhoff矩阵任何一个n－1阶主子式的行列式的绝对值。即:

式中，为图G的生成树数目，Cj为图G的Kirchhoff矩阵任何一个n－1阶主子式。

2 两测度法

所谓的两测度分别是指当链路失效时整个网络的生成树数目以及图中节点两两之间最短距离的总和。因此，一条链路的重要性可定义为:

ti代表当网络中第i条链路失效时整个网络的生成树数目，di当网络中第i条链路失效时图中节点两两之间最短距离的总和，Ri定义为第i条链路的重要程度。但是当网络规模较大时，网络的生成树数目会很大，不利于数据统计，因此可将链路的重要性归一化为:

t表示网络中全部链路都正常工作时图的生成树数目，ti表示网络中全部链路都正常工作时网络中全部节点两两之间最短距离的总和。由于ti与链路的重要性成反比，di与链路的重要性成正比关系，故ri的值越小代表链路越重要。

令无线传感器网络的抽象模型为无自环连通图G。

输入:图G的完全关联矩阵。

输出:按重要性的大小输出每条链路的重要性归一化后的结果。

(1)输入G的完全关联矩阵。

(2)计算图G的生成树数目t以及全部节点两两之间最短距离的总和d。

(3)删除需要评估的链路。

(4)计算链路i删除后图的生成树数目及全部节点两两之间最短距离的总和d。

(5)计算链路的归一化的结果。

(6)若还有链路未计算，则返回第三步;若全部链路都已经计算完毕，程序终止。

3 实验仿真

对算法进行说明如图1所示。图1(a)为系统随机产生的一个有向图，图1(b)为在节点V3和V10间删除链路e15后生成的图的拓扑结构。图1(a)共有11个节点和15条链路，删除链路e15后节点和链路的数目分别变为11和14。以链路e15为例，删除后分别计算其生成树的数目，全部节点两两之间最短距离的总和，并作归一化处理，其值作为链路e15的重要性的评价标准。运用本文算法对图1进行链路重要性的评估，并对比文献1，结果如表1所示。

图1 链路有向图G

表1 无线网络中不同方法的链路重要性比较

对算法进行说明如图2所示。采用Hasse图对图1的链路重要性进行排序(由公式(4)可知归一化结果越小则节点越重要)，结果如图2(a)所示，自上到下代表链路的重要性从高到低。对比链路删除法的算法对图1重要性评价的结果可以得出图2(b)，比较可知，本文的算法在对链路的重要性的评估上与文献1是趋向一致的。进一步比较每条链路的重要性，由表结果表明，删除链路e4后，由链路删除法可知e4、e5、e6所对应的归一化结果最小，可知e4、e5、e6是等重要的链路，而由两测度法可知e4所对应的归一化结果最小，可知e4是最重要的链路。通过比较可以发现，与链路删除法相比，两测度法具有更高的精确度。由两测度法易知，在网络发生故障时各条链路的维修的先后顺序，以使网络遭受的损失最小，提高网络的可靠性。

图2 链路重要性排序结果

4 结束语

本文提出了一种评价网络中链路重要性的新方法，并给出了归一化的表达式。通过比较生成树的增加数目和全部节点两两之间最短距离的总和，可以比较网络中任意条链路的相对重要性。在评价链路重要性的同时，还解决了串联链路的等重要性问题，进一步区分重要性，与文献1相比更具有实用性，是一种可靠的链路重要性评价方法。

［1］ Tsen F P，T Y Sung，M Y Lin，et al.Finding the most vital edges with respect to the number of spanning trees［J］.IEEE Trans Reliability，1994，43(4):600 －602.

［2］ 陈勇，胡爱群，胡骏.通信网中最重要节点的确定方法［J］.高技术通讯，2004，14(1):21－24.

［3］ 陈四军，贾连兴，李晶晶.基于通信网抗毁性的链路重要性比较［J］.计算机工程与应用，2009，45(1):118－120.

［4］ 李方敏，刘新华，徐文君，等.无线传感器网络的链路稳定成簇与功率控制算法［J］.计算机学报，2008，31(6):969－978.

［5］ 任智，郭伟，苏静，等.基于跨层协同设计的高效AODV改进路由算法［J］.计算机学报，2007，3(5):839－843.