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

于冲 等:基于二跳共同邻居的无人机群体网络演化算法 3565

C = g {h v∈ :|| p − g p h ||≤ R ∩ ( , ) h ∉ } ε
g
calculate P rep (, )g h = T C _( , )h g ∑ T C _( , )u g
uC g
∈
find max P rep (g,h)

(g,h) join ε
3 网络可靠性的数学证明

根据本文所提出的网络演化模型我们可以知道:对于任意一个集合 v 中的节点 y 来说,导致其度值变化的
原因主要分为 3 个方面.
(1) 新加入的节点 x 以一定的概率选择与节点 y 建立连接.由于节点均匀的分布在边长 L 的立体空间中,
3
3
所以新加入的节点 x 在节点 y 通信范围内的概率为 V/L ,V=4πR /3 表示节点的通信范围.除此以外,

新加入的节点 x 将与 v 中的 m 个节点形成连边,故 v 中所有节点与节点 x 产生连接的概率将扩大 m
3
倍,从而我们能够得到节点 x 与节点 y 产生连接的可能性为 mP x,y V/L .
(2) 由于节点故障失效等原因,会出现节点 y 自身连边丢失的情况,导致其度值发生变化.节点 y 在执行任
务的工作中可能出现节点故障等状况,此时,与之相关的连接将全部断开,假设节点发生故障的概率
为ρ,那么由节点故障导致的度值减少量可以表示为ρk y .
(3) 节点 y 的邻居节点中,有节点需要重新建立连边,节点 y 作为候选节点有一定概率被选中进行连边重
建.节点通信范围内所有节点的度值总和为 ∑ k ,由于节点 y 自身发生故障属于第(2)种情况,因
∈
wN y w
此我们需要从 ∑ k 中将 k y 去除.用 p dis 表示节点之间不存在连边的概率,那么节点 y 作为连边重
∈
wN y w
建的候选节点的概率可以表示为 ρ ⋅ p (∑ k − k ) .在此基础上,得到节点 y 被选中进行连边重建
∈
dis wN y w y
的概率为 ρ ⋅ p (∑ k − k y P (, ) y .
w
∈
dis wN y w ) rep
根据文献[20],我们假设节点的度值变化是连续的,则无人机节点 y 的度值变化率可以表示为
k ∂ V T ⎛ k − k ⎞ ∑ T
y = m C _( , )y x − ρ k + y ρ ⋅ p dis ⎜ w y ⎟ C _( , )y w (9)
t ∂ L ∑ 3 T C _( , ) x ⎝ wN y ⎠ ∑ T C _( , )
∈
z
s w
∈
∈
zN x s C w

由于每单位时间集合 v 中新增一个节点,所以 t 时刻 v 中的节点总数为(m 0 +t).如第 1.1 节中所述,两个节点
3
之间的平均重叠范围为Ω,以此推断,新加入的节点 x 与候选节点 y 的平均共同邻居数为(m 0 +t)Ω/L .节点 y 的度
值 k y 代表 E y 中的节点总数为 k y ,那么节点 x 与节点 y 的平均二跳共同邻居数可以表示为
T C _( , ) x ≈ C N _( , ) y = ∑ k y (m + 0 ) t Ω / L 3 (10)
y
z
∈
≠
zE x ,z y
初始时刻,网络中存在 m 0 个节点,每个新加入的节点需要与网络中现有节点建立 m 条连边.t 时刻,网络中存
在的连边总数与度值总数分别为 mt 和 2mt,此时,网络中节点度值的平均值可以表示为 2mt/(m 0 +t).随着 t 的不断

增大,初始节点数 m 0 对平均度值的影响作用越来越小,因此我们将平均度值近似为 k = 2m ,则集合 v 中任意节
点与新加入节点 x 之间存在的平均二跳共同邻居数量为 (km + ) t Ω / L .对于网络中的任意节点,其候选节点集
3
0
3
合中的节点总数为 W=(m 0 +t)V/L ,故有:
T C _( , ) x ≈ ∑ Wkm + ( 0 ) t Ω / L = 3 ( km + 0 ) t 2 VΩ (11)
z
6
∈
zN x L
∑ wN y k 表示节点 y 通信范围内所有节点的度值总和,其数值可以由节点 y 通信范围内的节点个数与节点平均
w
∈
度值的乘积表示,即
k = ∑ w Wk = 2(mm + ) t V (12)
0
3
∈
wN y L
通过上述推导我们可知:节点 w 通信范围内存在的节点个数为 W,并且节点 w 的平均度值为 2m,则节点 w