中国学术期刊网 » 论文 » 工学论文 » 通信论文 » 基于有向通信网络的传输链路重要性评价分析论文正文

基于有向通信网络的传输链路重要性评价分析

中国学术期刊网【通信论文】 编辑:天问 云南大学学报(自然科学版) 2016-11-02基于有向通信网络的传输链路重要性评价分析论文作者:张强 龙华 王晨歌 邵玉斌,原文发表在《云南大学学报(自然科学版)杂志》,经中国学术期刊网小编精心整理,仅供您参考。

关键词: 链路重要性; 有向网络; 路由; 网络传输; 通信
摘要:为了方便分析有向通信网络的链路重要性,提出一种基于有向通信网络的链路重要性评价方法.该方法首先利用每条子链路的传输概率计算出各链路的信息量,并且将其作为链路权重值;然后利用提出的链路计算方法,寻找出初始节点与目的节点全部传输路由,将每条链路中的子链路分别进行对应的加权后求和得到各链路总权重值,并将总权重值取倒数得到链路的评估系数,依据所定义的链路重要性,通过每条链路的评估系数对链路进行重要性评价.计算实例表明,该方法能有效地对通信网络链路的重要性进行评价,具有一定的有效性和实用性.

中图分类号:TP951.02 文献标志码:A 文章编号:0258-7971(2016)05-0724-06 doi: 10.7540/j.ynu.20160096

对通信网络链路重要性分析的传统研究方法, 都是通过链路删除或者链路收缩后对网络架构的连通性造成的影响大小进行.目前常用的通信链路重要性评价准则有:最短路径法[1]、最小路集-割集法[2]、最小生成树权重法[3]等.但这些评价方法很少从链路所传信息量的多少对链路进行重要性评价.文献[4]与文献[5]对链路重要性分析的研究都只针对于各网络节点间的直接相连的链路, 而没有对起始节点与目的节点所有可能的传输链路重要性进行研究分析, 这样易导致局部性地对链路重要性进行评价而不是从全局的概念对链路进行重要性评价, 这种方式在实际应用中往往易产生评价误差.文献[6]提出的根据链路在网络所有节点间相互通信过程中最短路径被使用的频度进行链路重要性评价, 该方法虽然可以评价任意2条链路的相对重要性, 但却不能对两节点间所有可能的传输链路的重要性进行评价, 且文献[4, 5, 6]都没有针对链路所传信息量的多少对传输链路进行评价.Dijkstra与Floyd算法是最短路径寻找方法的代表, 在Internet网络路由中被广泛采用[7].最短路径[8, 9]寻找方法只能评价通信链路最短路径的重要性, 而无法进行全网范围的链路重要性评价[6].

本文提出一种快速寻找两节点间所有传输链路的计算方法, 并把通信链路传输的信息量作为传输链路的权重值应用至网络链路重要性评价分析中.

1 有向网络链路重要性评价模型的建立
1.1 权重矩阵的确定
有向通信网络通常描述为一个有向图G=(V, E)[10], 其中V表示图的所有顶点的集合, 图的顶点对应网络的节点; E表示图的所有有向边的集合, 图的边对应网络的链路.

Step 1:建立网络节点关系模型

对一个具有m个节点的网络拓扑图建立一个概率传输方阵A=[P(ai, aj)]m× m, 其中P(ai, aj)表示节点ai传递信息至aj的概率.

Step 2:确定权重函数F[P(ai, aj)]

事件的不确定程度可以用事件出现的概率来描述, 信息量是对消息发生的概率的度量, 消息中包含的信息量与消息发生的概率密切相关[11], 消息出现的概率越小, 则消息中包含的信息量就越大; 反之, 消息出现的概率越大, 则消息中包含的信息量就越小.数学家香农在题为“ 通讯的数学理论” 的论文中指出:“ 信息是用来消除随机不定性的东西” [12].由信息的定义可知, 在通信过程中, 收信者所获取的信息量, 在数量上等于通信前后不确定性地消除.定义一个m阶方阵B=[b(ai, aj)]m× m, 其中每个元素b(ai, aj)表示从节点ai到aj的链路权重F[P(ai, aj)], 假定节点ai和节点aj, 以及节点aj和节点ak的传输先验概率分别为P(ai, aj)和P(aj, ak), 且满足0≤ P(ai, aj)≤ 1、0≤ P(aj, ak)≤ 1, F[P(ai, aj)]满足以下条件:

条件1:若P(ai, aj)< P(aj, ak), 则:

F[(P(ai, aj)]> F[(P(aj, ak)];

即函数F[(P(ai, aj)]是先验概率P(ai, aj)的单调递减函数.

条件2:2个节点间不存在信息传输时其链路权重为无穷大, 即在P(ai, aj)=0时, 有:F[P(ai, aj)]→ ∞ ;

条件3:2个节点间以概率1传输信息时, 该链路权重为0, 即P(ai, aj)=1时, 故有:F[P(ai, aj)]→ 0;

条件4:在网络节点拓扑图中, 相邻的2条链路之和F[P(ai, aj)]+F[P(aj, ak)]与相邻链路的自变量的联合概率有关, 即:

F[P(ai, aj; aj, ak)]=F[P(ai, aj)]+F[P(aj, ak)];

根据以上可总结出, 满足上述条件的映射关系的权重函数F[P(ai, aj)]应为:

F[P(ai, aj)]=log 1p(a i ,a j ) 1p(ai,aj)=-logP(ai, aj).

Step 3:根据权重函数, 将概率传输方阵转换为网络拓扑图的权重矩阵B=[b(ai, aj)]m× m.

1.2 计算初始节点与目的节点的全部路由
Step 1:构建网络关联矩阵

对一个具有m个节点的网络拓扑图建立一个关联矩阵, 其表示为:C=[e(ai, aj)]m× m其代表节点ai至节点aj的直接相连的链路, 对于方阵的建立, 遵循以下规则:

(1) 元素定义为:e(ai, aj)= {0;若节点a i 与节点a j 间无直接链路e k ;若节点a i 与节点a j 间有直接链路e k 0;若节点ai与节点aj间无直接链路ek;若节点ai与节点aj间有直接链路ek;

(2) 若节点ai至节点aj之间有多条边, 比如存在边es、ek, 则对2条边进行逻辑“ 或” 运算, 即e(ai, aj)=es⊕ek;

(3) 将终点作为第m个节点, 即关联矩阵的第m列反映了终点的连接状况.

Step 2:关联矩阵节点的消除变换

对关联矩阵进行节点的消除主要是为了关联矩阵降阶.

(1) 寻找2个节点间的路由, 则需要将这2个节点之间的所有中间节点消除, 如果欲消除节点ai与节点aj之间的节点ak, 则可以按照以下逻辑运算规则进行新关联矩阵中元素的生成:e(ai, aj)=e(ai, ak)· e(ak, aj) ⊕ e(ai, aj), 其中“ · ” 表示逻辑“ 与” 运算, “ ⊕” 表示逻辑“ 或” 运算, e(ai, aj)表示消除节点ak后产生的新关联矩阵的元素, 该过程目的是将经过节点ak的链路融合至新的关联矩阵中, 进而将关联矩阵降阶, 生成新的关联矩阵;

(2) 消除节点ak, 意味着删除原关联矩阵的第k行和第k列, 按照1所述方式, 最终得到只剩起始节点和目的节点的一个二阶矩阵, 将二阶矩阵除起始节点与目的节点对应的矩阵元素外的其余元素归零.此时该二阶方阵中只剩下一个非0元素, 将这个非0元素进行逻辑运算化简, 这个元素即表示起始节点和目的节点的所有连接状况, 将所有逻辑“ 或” 拆分, 拆分后而形成的所有逻辑“ 与” 表达式即为起始节点与目的节点之间的全部可能传输链路.

2 链路重要性分析
为方便对链路重要性进行分析, 本文作出如下假设:

(1) 网络节点认为是完全可靠, 且有足够容量;

(2) 网络都是有向的;

(3) 网络节点自身不存在环路.

一条完整的通信网络链路定义为初始节点至目的节点间进行通信时通过的所有子链路的有序组合, 对于完整的通信网络链路来说, 子链路信息量越大, 表示子链路的权重值越大, 对应的该完整的链路总权重值也越大, 意味着信息通过此链路传输的概率越小, 链路相对整个网络架构来说重要性较低; 反之, 子链路的信息量越小, 表示子链路的权重值越小, 对应的完整的通信链路权重也越小, 意味着信息通过此链路传输的概率越大, 此时链路相对整个网络架构来说重要性更高.因此将链路重要性定义为与每条完整链路的评估系数相关, 评估系数为每条完整链路的总权重值, 总权重值越大, 对应的评估系数越小, 表示该完整链路的重要性相对较低; 反之, 总权重值越小, 对应的评估系数越大, 表示该完整链路的重要性相对较高.依据链路重要性定义, 对1.2所产生的起始节点与目的节点的全部传输链路, 根据网络拓扑图的权重矩阵B=[b(ai, aj)]m× m, 将权重矩阵中对应的权重元素值代入各传输链路的子链路中, 并对各个传输链路中各个逻辑“ 与” 运算的子链路的权重值进行算术相加得出各传输链路的总权重值, 通过将总权重值取倒数得到评估系数, 然后将根据各链路的评估系数进行路径重要性评价, 评估系数越大, 传输链路对网络的重要性越高; 反之, 评估系数越小, 传输链路对网络的重要性越低.在进行网络信息传输时, 可据此来考虑链路的择取使用.

3 传输链路重要性评价分析实例计算
通过图1的有向网络拓扑图, 对传输链路重要性的评价计算过程进行分析和验证, 这里假设寻找节点a1至节点a5的全部传输链路, 并通过计算对传输链路重要性进行分析, 图1中e1、e2、e3、e4、e5、e6、e7、e8、e9、e10、e11定义为通信网络信息传输的子链路.


图1
Fig.1
Figure OptionView
Download
New Window
图1 有向网络拓扑图
Fig.1 Directed network topology

Step 1:根据1.1节所述步骤, 对有向网络拓扑图1建立概率传输矩阵A:

A=a1 a 1 00.3000 a 2 0.200.30.10 a 3 0.10.6000.5 a 4 00.220.600.2 a 5 0000.40 a1a2a3a4a500.20.1000.300.60.22000.300.6000.1000.4000.50.20.

Step 2:根据概率传输矩阵计算规则计算出权重矩阵B:

B=m1 m 1 ∞0.523∞∞∞ m 2 0.699∞0.5231∞ m 3 10.222∞∞0.301 m 4 ∞0.222∞0.699 m 5 ∞0.658∞0.398∞ ∞ m1m2m3m4m5∞0.6991∞∞0.523∞0.2220.658∞∞0.523∞0.222∞∞1∞∞0.398∞∞0.3010.699∞.

Step 3:根据1.2节所述规则, 对图1构建关联矩阵C, 本例中需要消除节点a2、节点a3, 以及节点a4, 以达到将关联矩阵降C阶的目的:

A=a1 a 1 0e 1 000 a 2 e 2 0e 5 e 6 0 a 3 e 3 e 4 00e 9 a 4 0e 7 e 8 0e 11 a 5 000e 10 0 a1a2a3a4a50e2e300e10e4e700e50e800e600e1000e9e110.

(1) 取ak=a2, 消除节点a2, 将关联矩阵C降为4阶, 得到表示节点a1、节点a3、节点a4及节点a5连接状况的新关联矩阵C1:

C1= e 2 ⋅e 1 e 5 ⋅e 1 e 6 ⋅e 1 0 e 2 ⋅e 4 ⊕e 3 e 5 ⋅e 4 e 6 ⋅e 4 e 9 e 2 ⋅e 7 e 5 ⋅e 7 ⊕e 8 e 6 ⋅e 7 e 11 00e 10 0 e2·e1e2·e4⊕e3e2·e70e5·e1e5·e4e5·e7⊕e80e6·e1e6·e4e6·e7e100e9e110.

(2) 取ak=a3, 消除节点a3, 将关联矩阵C1降为3阶, 得到表示节点a1、节点a4及节点a5连接状况的新关联矩阵C2:

C2= e 2 ⋅e 4 ⋅e 5 ⋅e 1 ⊕e 3 ⋅e 5 ⋅e 1 e 6 ⋅e 4 ⋅e 5 ⋅e 1 e 9 ⋅e 5 ⋅e 1 e 2 ⋅e 4 ⋅e 5 ⋅e 7 ⊕e 2 ⋅e 4 ⋅e 8 ⊕e 3 ⋅e 5 ⋅e 7 ⊕e 3 ⋅e 8 e 6 ⋅e 4 ⋅e 5 ⋅e 7 ⊕e 6 ⋅e 4 ⋅e 8 e 9 ⋅e 5 ⋅e 7 ⊕e 9 ⋅e 8 ⊕e 11 0e 10 0 e2·e4·e5·e1⊕e3·e5·e1e2·e4·e5·e7⊕e2·e4·e8⊕e3·e5·e7⊕e3·e80e6·e4·e5·e1e6·e4·e5·e7⊕e6·e4·e8e10e9·e5·e1e9·e5·e7⊕e9·e8⊕e110.

(3) 取ak=a4, 消除节点a4, 将关联矩阵C2降为2阶, 将二阶矩阵除起始节点与目的节点对应的矩阵元素外的其余元素归零, 并将剩余的一个非零元素进行逻辑简化, 得到表示节点a1和节点a5连接状况的新关联矩阵C3:

C3= [00 e 2 ⋅e 4 ⋅e 5 ⋅e 7 ⋅e 10 ⊕e 2 ⋅e 4 ⋅e 8 ⋅e 10 ⊕e 3 ⋅e 5 ⋅e 7 ⋅e 10 ⊕e 3 ⋅e 8 ⋅e 10 0 ] 0e2·e4·e5·e7·e10⊕e2·e4·e8·e10⊕e3·e5·e7·e10⊕e3·e8·e1000.

从关联矩阵C3中可以得出节点a1至节点a5的由子链路连接而成的全部传输链路, 即关联矩阵C3中用“ 逻辑或” 连接的4个“ 逻辑与” 表达式:

L1=e2· e4· e5· e7· e10,

L2=e2· e4· e8· e10,

L3=e3· e5· e7· e10,

L4=e3· e8· e10.

通过列表法和图解法都可以得到和上述相同结果的传输链路, 将权重矩阵中对应的权重元素值代入各传输链路的子链路中, 并对各个传输链路中各个逻辑“ 与” 运算的子链路的权重值进行算术相加得出各传输链路的总权重值:

M(L1)=B(1, 2)+B(2, 3)+B(3, 2)+B(2, 4)+B(4, 5)=0.699+0.222+0.523+0.658+0.398=2.5,

M(L2)=B(1, 2)+B(2, 3)+B(3, 4)+B(4, 5)=0.699+0.222+0.222+0.398=1.541,

M(L3)=B(1, 3)+B(3, 2)+B(2, 4)+B(4, 5)=1+0.523+0.658+0.398=2.579,

M(L4)=B(1, 3)+B(3, 4)+B(4, 5)=1+0.222+0.398=1.62.

对总权重值取倒数得到相应完整链路的评估系数:

S[M(L1)]= 1M(L1) 1M(L1= 12.5 12.5=0.4,

S[M(L2)]= 1M(L2) 1M(L2= 11.541 11.541=0.649,

S[M(L3)]= 1M(L3) 1M(L3= 12.579 12.579=0.388,

S[M(L4)]= 1M(L4) 1M(L4= 11.62 11.62=0.617.

Step 4:链路重要性分析:定义每条链路子链路的权重值和为每条链路总权重值M(L), L代表链路, 对于链路L1而言:节点a1与节点a5依次通过子链路e2、子链路e4、子链路e5、子链路e7、子链路e10进行信息传输, 其对应的总权重值M(L1)=2.5, 其对应的评估系数S[M(L1)]=0.4; 在链路L2中, 节点a1与节点a5依次通过子链路e2、子链路e4、子链路e8、子链路e10进行信息传输, 其对应的总权重值M(L2)=1.541, 对应的评估系数为S[M(L2)]=0.649; 在链路L3中, 节点a1与节点a5依次通过子链路e3、子链路e5、子链路e7、子链路e10进行信息传输, 其对应的总权重值M(L3)=2.579, 对应的评估系数S[M(L3)]=0.388; 在链路L4中, 节点a1与节点a5依次通过子链路e3、子链路e8、子链路e10进行信息传输, 其对应的总权重值M(L4)=1.62, 对应的评估系数S[M(L4)]=0.617; 对比这4条链路的权重值, 链路的总权重值由高至低依次是L3、L1、L4、L2, 所含未知信息量由高至低的链路依次是L3、L1、L4、L2, 对应的评估系数由高至低的顺序依次为L2→ L4→ L1→ L3, 则各链路对于网络的重要性按从高至低的顺序为L2→ L4→ L1→ L3, 在进行网络信息传输时, 可依据此重要性选择最佳信息传输链路.

4 结束语
本文从起始节点与目的节点的链路所含信息量总和的大小, 对网络起始节点与目的节点的链路重要性进行评价分析, 计算起始节点与目的节点的链路算法简单, 运算1次即可将起始节点与目的节点间的全部传输链路求出.通过寻找得到所有起始节点与目的节点间的路由, 并将信息在每条子链路的传输概率转换成权重值, 代入起始节点与目的节点的所有相对应的子链路中并对链路求和, 将得到的各链路的总权重值进行取倒数得到评估系数, 根据各链路评估系数的大小对链路重要性进行评价, 链路评估系数越大, 链路的重要性越高; 反之, 链路评估系数越小, 链路的重要性越低, 可为最佳传输链路的选择提供参考.从方法和原理上讲, 本文所提出的基于有向通信网络的链路重要性评价方法只考虑了有向通信网络, 其在无向网络等其它类型网络中能否适用还需进一步研究.