Page 249 - 《软件学报》2020年第11期

3564 Journal of Software 软件学报 Vol.31, No.11, November 2020

甚至受到破坏.图 4 描述了无人机失效时,通信网络的变化情况.原始状态下,3 架无人机之间存在 3 条通信链路,
当其中一架无人机失效时,所有与此无人机相关的通信链路将不复存在.此时,通信网络的完整性受到了破坏.
因此,我们要采取适当的手段对网络进行维护和修复,进而保持集群通信网络结构的完整与可靠.

Fig.4 Change of net topology
图 4 网络拓扑变化

存在以下 3 种场景会造成通信网络拓扑结构的变化.
(1) 无人机个体加入或脱离集群.根据任务的难易程度、执行的进度等情况,集群会选择增加或者减少无
人机的数量,在保证完成任务的同时降低成本.
(2) 无人机节点发生故障.无人机在运行过程中,零部件的损坏以及能源燃料不足等问题,都会造成无人
机无法正常运转.
(3) 无人机受到攻击.在执行军事战斗、情报侦察等特殊任务的情况下,无人机会受到来自于敌方军事系
统的干扰或攻击,这将导致无人机彻底丧失进攻与收集信息能力.
由于场景(2)、场景(3)这两种情况对网络的影响更为明显,所以本文着重关注这两种情况下通信网络的修
复问题.
定义 v′ = {: ( , )j i j ∈ } ε 表示与节点 i 存在通信连接的全部节点所构成的集合.假设在某一时刻无人机 i 失效,

从集合 v 中删除节点 i,同时,集合 ε 中所有包含节点 i 的连边被删除,此后,v′中的节点将被赋予新的连边.依次遍
历集合 v′中的节点执行网络修复算法,g 表示当前遍历的节点,受到节点通信能力的限制,只有在节点 m 通信范
围内的节点可以作为建立连接的候选节点,候选节点的集合可以表示为 C = {h v∈ :|| p − p ||≤ R ∩ ( , )g h ∉ } ε ,
g g h
候选节点与节点 g 的连接概率表示为
T C _( , )h g
g
P rep (, ) h = (8)
∑ T C _( , ) g
u
uC g
∈
比较所有候选节点的连接概率,选取连接概率最大的候选节点与节点 g 建立连接.整个网络演化算法伪代
码如算法 1.
算法 1. 网络演化算法.

( , )
initialize: v and Gv ε

v
while ( !v = )

picks a random x v∈ and x v∉

for each y ∈
v

if ( (, :yz z ∈ ) v ∈ ε )
N y add z
=
calculate T _( ,)y x ∑ C
∈
≠
C zN y ,z x N _( ,)z x
find max T C_(y,x)

x join v , (x,y) join ε
if remove i

v′ = {: ( , ) j ∈ j i } ε , v delete i, ε delete (i,j)
for each g∈v′