无线传感器网络(wireless sensor network, 简称WSN)是由大量传感器节点以自组织多跳的方式构成的无线网络^[1], 它能够将逻辑的信息世界与客观的物理世界紧密地融合在一起, 使人们从更加微观的角度了解周围环境^[2], 被广泛地应用于国防军事、环境监测、交通管理、医疗卫生、反恐抗灾等领域.

连通性作为WSN服务质量重要的度量指标, 决定了传感器节点所采集到的信息能否及时准确地传递到基站(base station, 简称BS), 是WSN应用的前提^[3].然而在某些WSN实际应用中, WSN可能因大量节点同时失效而产生大规模毁坏, 致使网络剩余存活传感器节点被分割成多个不连通的网络孤岛^[4], 此现象被称为孤岛效应, 如图 1所示.因此, 将各网络孤岛进行结盟, 重新恢复WSN的连通性, 对WSN恢复机能具有至关重要的意义.

现有的WSN连通性修复方法可分为两类:一类是剩余节点重定方法, 另一类是额外中继部署方法.剩余节点重定位方法是以重定位网络中剩余存活节点位置的方式来重建网络连通性^[5-7], 然而当网络因大规模毁坏而形成多个孤岛时, 此类方法无法有效地修复网络连通性, 这是因为传感器节点自身的资源和能力受限, 无法移动较长的距离; 额外中继部署方法是在满足某些条件约束下, 以向受损区域部署额外中继的方式来修复网络连通性, 此类方法所形成的修复网络拓扑结构扩展性强, 十分适用于自组织网络的孤岛结盟.Cheng等人^[8]以最少中继部署数量为优化目标, 将WSN孤岛结盟描述为最少Steiner点的Steiner最小树问题(SMT-MSP), 并以单位圆覆盖模型为基础, 设计了该问题的近似求解算法.Efrat等人^[9]以Steiner最小树路径为中继部署约束, 对文献[8]进行扩展, 并给出了一种近似求解算法.Jehan等人^[10]从提高网络鲁棒性角度出发, 对文献[9]的近似求解算法进行了改进.文献[8-10]虽然以最少中继数量实现孤岛结盟部署, 但缺乏网络QoS方面的考量.Lee等人^[11]以最少中继部署数量为优化目标, 以2-连通为约束条件, 提出了CRAFT优化问题, 并给出了近似求解算法及相关性能分析.Joshi等人^[12]在CRAFT的基础上进行扩展, 增加了异构通信半径约束, 并给出了近似求解算法.文献[11, 12]虽然以连通度QoS为约束, 以最少中继部署数量为目标, 实现了孤岛结盟部署, 但缺乏考量制约孤岛结盟效率的带宽QoS约束.Lee等人^[13]首次提出了一种能够同时满足孤岛间连通性和带宽约束的中继部署问题, 并给出了一种近似求解算法.Lee等人^[14]将文献[13]扩展为具有双重连通性和带宽约束的中继部署问题(OBiC), 并给出了一种近似求解算法.文献[13, 14]虽然在文献[11, 12]所提出的优化问题基础上增加了孤岛带宽约束, 但随着数据融合技术^[15]的广泛应用, 不同规模孤岛之间的带宽差异并不显著, 反而这些方法对中继带宽的零约束不仅影响了孤岛结盟方法在资源受限网络中的适用性, 还严重地降低了孤岛的结盟效率.此外, 在孤岛分布未知的情况下, 现有孤岛结盟方法的适用性受到了严重制约, 而孤岛搜索作为突破该制约的关键, 常从空间和时间上独立于孤岛结盟, 作为其前提假设而存在, 这也无形中降低了现有孤岛结盟方法的效率.

针对上述孤岛结盟方法的不足之处, 我们提出了基于搜索带宽感知的多机器人WSN孤岛结盟优化问题(multi-robot federating for disjoint segments in WSN based on search and bandwidth aware, 简称MRF-SNSA).该问题从多机器人孤岛搜索与中继部署的并行性及中继数量最优性两个层面出发, 对现有孤岛结盟方法进行改进, 以提高未知环境中具有中继带宽约束的WSN孤岛结盟适应性和效率.本文的主要贡献包括以下几点.

(1) 为提高现有WSN孤岛结盟方法的适应性和效率, 提出了MRF-SNSA问题, 并在搜索带宽感知模型基础上, 结合约束最优化方法, 给出了该问题的公式化描述;

(2) 为了近似求解该最优化问题MRF-SNSA, 基于层次分簇和网络流相关理论, 设计了一种基于搜索带宽感知的层次中继部署算法;

(3) 从中继部署数量和中继部署时间两个评价指标出发, 与现有的WSN孤岛结盟方法进行对比仿真和实际实验, 验证所提出方法的有效性.

与已有方法相比, 本文方法的特点在于:

(1) 已有方法通常以孤岛分布作为先验知识, 利用无带宽约束中继进行WSN孤岛结盟, 本文方法对这两种非理想假设没有限定, 具有较强的实际应用能力和适应能力;

(2) 已有方法通常将WSN孤岛结盟与获取孤岛分布的孤岛搜索割裂为两个时空无关联的独立问题, 相比之下, 本文方法借鉴迭代局部搜索和流水作业调度思想, 深度分析孤岛搜索与结盟的时空关系, 以轮次流水迭代方式, 并行执行孤岛搜索与结盟过程, 有效地提高WSN孤岛结盟效率;

(3) 已有方法由于没有中继带宽约束, 通常不强调已部署中继利用率, 相比之下, 本文方法虽然限定了中继带宽, 但由于其充分利用了已部署中继带宽, 非但没有因增加约束条件而增加中继部署数量, 反而有益于节省硬件成本, 提高孤岛结盟效率.

1 系统模型及问题公式化描述

首先给出系统相关模型假设, 并在此基础上, 借鉴迭代局部搜索和流水作业调度思想, 引入搜索带宽感知模型, 建立MRF-SNSA问题的公式化描述.

1.1 系统模型假设

(1) 网络模型

WSN由n个传感器节点和一个基站(base station, 简称BS)组成, 且所有节点随机分布于一个M×M感知区域A内; WSN的MAC层采用IEEE802.15.4标准, 网络层采用TEDG-WMR数据收集协议^[16]; WSN被抽象为连通图G(S, E), 其中, S={s₁, s₂, ..., s_n}是感知区域A内的所有节点集合, E是连接节点间边的集合.此外, 节点具有相同的最大感知半径R_s和通信半径R_c, 且可通过定位算法获知自身位置.

(2) 机器人模型

感知区域A中存在m个机器人r={r₁, r₂, ..., r_m}, 通信半径和感知半径分别为r_c和r_s, 且其可在T_d时间内完成移动、通信、感知、搜索、部署等行为; 根据算法调度策略, 机器人可在搜索机器人(robot-assisted search, 简称RAS)和中继部署机器人(robot-assisted rely deployment, 简称RARD)两种角色间转换, 且在其移动时忽略加速度和制动时间, 即移动速度v恒定不变.此外, 我们假设机器人所部署的中继为普通传感器节点, 且其负载和通信能力足以满足MRF-SNSA求解需求.

(3) 孤岛模型

为了降低孤岛结盟问题的复杂性, 我们从孤岛自身连通特性出发, 将孤岛结盟研究对象中的任意孤岛Seg_i简化为代表节点S_i.由于孤岛网络层协议与WSN一致, 即为TEDG-WMR, 故我们充分利用其层次分簇的特点, 以每个孤岛的簇头集合为候选代表节点集合CH_Seg(i), 并在RAS搜索时, 将与RAS距离最小的候选代表节点作为代表节点S_i.此外, 我们假设孤岛内传感器节点所感知的数据仅从其代表节点向外转发, 且其网络流量输出率为rate_send.

(4) 环境模型

基于地图表示理论^[17], 以RAS感知半径的最大内切正方形为基本单元, 将感知区域A网格化为一个由基本网格单元组成的网格地图, 并在此基础上, 结合连通重叠搜索算法^[18]中所定义的网格单元状态(未搜索、正在搜索和已搜索), 将时间间隔T_sti内RAS已搜索且仅有一个未搜索邻接单元的网格定义为边界网格单元, 并将由其所组成的网格单元集合称为边界网格单元集合, 由C_frn表示.在MRF-SNSA问题中, 我们将RAS搜索孤岛、感知边界网格单元并移动到最优边界网格单元的过程称为RAS搜索感知.

(5) 拓扑模型

机器人和传感器节点均采用Unit Disk Graph拓扑模型^[19], 且机器人的网络流量输出率为rate_send, 中继链接容量为rate_capacity.在MRF-SNSA问题中, 由机器人、孤岛和BS所形成的结盟网络拓扑需要同时满足:

约束(1):在T_sti内, RAS与BS之间是连通的;

约束(2):RARD所部署中继的最大网络流承载数量K≤⌊rate_capacity/rate_send⌋, 即中继带宽.

此外, 我们将孤岛结盟过程中同时满足约束(1)和约束(2)的RARD中继部署过程称为具有连通和带宽约束的RARD中继部署(以下简称RARD中继部署).

1.2 问题公式化

作为分析求解MRF-SNSA问题的基础, MRF-SNSA公式化描述起到至关重要的作用.我们在第1.1节系统模型假设的基础上, 给出相关符号及定义(见表 1), 并以提高孤岛结盟效率为核心, 借鉴迭代局部搜索^[20]和流水作业调度^[21]的思想, 阐述同步轮次流水迭代过程(如图 2所示), 引出搜索带宽感知模型, 建立MRF-SNSA问题的公式化描述.

在上述相关符号及定义基础上, 利用迭代局部搜索思想, 以连续两次边界网格单元变化为间隔, 将RAS搜索感知过程划分多个RAS搜索感知子过程, 并结合流水作业调度思想, 通过合理分配机器人角色, 以子过程一次重叠的方式, 按轮次与RARD中继部署进行同步, 该过程被称为同步轮次流水迭代, 如图 2所示.

在图 2中, 横坐标为执行时间序列(亦是RAS/RARD轮次), 纵坐标为RAS搜索感知与RARD中继部署的执行步骤.由于采用一次重叠的流水作业调度方式, 故RARD总是为前一轮RAS搜索到的孤岛进行中继部署.此外, 由于每轮中RAS搜索感知与RARD中继部署执行步骤一致, 故以第t轮迭代为例, 结合表 1所给出的相关符号定义, 分别细化各执行步骤, 计算RAS搜索感知时间$(T_{RAS}^t + {T_{sti}})$和RARD中继部署时间$(|{R^t}|{T_d} + T_{RARD}^t)$, 形成MRF-SNSA问题的搜索带宽感知模型:

$T_{RARD}^t + |{R^t}| \cdot {T_d} = T_{RAS}^t + {T_{sti}}$

(1)

上述搜索带宽感知模型(1)并不适用于第0轮和最后一轮, 然而这并不影响该公式的推广, 这是因为第0轮的RAS搜索感知时间和最后一轮的RARD中继部署时间之和相对较小, 所引起的总体效率延迟并不明显.另一方面, 相关算法运行时间与机器人中继部署时间相差两个数量级左右, 对评估MRF-SNSA总体效率影响甚微, 因此, 本文为了简化问题复杂度, 一并将它们忽略不计.

结盟效率作为评价孤岛结盟方法的重要度量指标, 可由多机器人在各孤岛之间建立结盟的时间总和表示; 且结合图 2中同步轮次流水迭代过程可知, 各轮次中RAS搜索感知与RARD中继部署同步进行, 故结盟时间可由每轮RARD中继部署时间$(|{R^t}|{T_d} + T_{RARD}^t)$之和表示.此外, 由于多机器人以并行方式执行中继部署, 且中继部署时间T_d恒定不变, 故在每轮结盟时间$(|{R^t}|{T_d} + T_{RARD}^t)$中, 新部署中继所消耗时间$|{R^t}| \cdot {T_d} > > T_{RARD}^t$, 因此, 结盟时间与中继部署数量|R^t|成正比例关系, 即MRF-SNSA结盟效率可直接由中继部署数量|R^t|决定.鉴于此, 我们在表 1符号定义和搜索带宽感知模型(1)的基础上, 将MRF-SNSA问题公式化为:从同时满足拓扑模型中两个约束的最优结构集合$\boldsymbol{CG}_V^t$中, 找到一组符合搜索带宽感知模型(1)的机器人最优结构$CG_{lopt}^t$, 使得每轮中所需部署的中继数量|R^t|最小的优化问题, 即:

●  目标函数:

$CG_{lopt}^t = \mathop {\arg \min }\limits_{C{G^t} \in \boldsymbol{CG}_V^t} \left( {\frac{{T_{RAS}^t + {T_{sti}} - T_{RARD}^t}}{{{T_d}}}} \right)$

(2)

●  约束条件:

$T_{RAS}^t = {{\sum\limits_{i = 1}^{|pCG_{RAS}^t|} {dist(q, i)} } \mathord{\left/ {\vphantom {{\sum\limits_{i = 1}^{|pCG_{RAS}^t|} {dist(q, i)} } v}} \right. } v}, \forall q \in C_{frn}^t, t \in {n_{it}}$

(3)

$\sum\limits_{i = 1, i \ne q}^{|pCG_{RAS}^t|} {Q(q, j)} \geqslant 1, \forall q \in C_{frn}^t, t \in {n_{it}}$

(4)

$|pCG_{{r_q}}^t - pCG_{{r_j}}^t| > 2{r_s}, \forall q \in C_{frn}^t, \forall j \in 1, ..., |pCG_{RAS}^t|, j \ne q, t \in {n_{it}}$

(5)

$\exists path(V), V=({{r}_{i}}\ \text{or}\ k, v_{1}^{t}, ..., v_{j}^{t}, ..., BS), \forall i\in 1, ..., m_{RAS}^{t}, \forall k\in Se{{g}^{t}}, {{v}_{j}}\in {{R}^{1, \ldots , t}}, t\in {{n}_{it}}$

(6)

$ dist({{v}_{j}}, {{v}_{j+1}})\le {{R}_{c}}, \forall {{v}_{j}}\in V, j\le |{{R}^{1, ..., t}}|, t\in {{n}_{it}} $

(7)

$\sum\limits_{i \in \{ r_1^t, ..., r_{m_{RAS}^t}^t\} \cup {R^t}} {|{f_{ij}}|} \leqslant K, \forall j \in {R^{1, \ldots , t}}, t \in {n_{it}}$

(8)

${{\left( {\sum\limits_{i \ne j} {{c_{ij}}{x_{ij}}\; + \;fm_{RARD}^t} } \right)} \mathord{\left/ {\vphantom {{\left( {\sum\limits_{i \ne j} {{c_{ij}}{x_{ij}}\; + \;fm_{RARD}^t} } \right)} v}} \right. } v} \leqslant (T_{RAS}^t + {T_{sti}}), i, j = 1, ..., |{S^t}|, t \in {n_{it}}$

(9)

$\sum\limits_{j = 2}^{|{S^t}|} {({x_{1j}} + {x_{j1}})} = 2m_{RARD}^t, j = 2, ..., |{S^t}|, t \in {n_{it}}$

(10)

$\sum\limits_{i \ne k} {{x_{ik}}} + \sum\limits_{j \ne k} {{x_{kj}}} = 2, i, j = 1, ..., |{S^t}|, k = 2, ..., |{S^t}|, t \in {n_{it}}$

(11)

$\sum\limits_{i \ne j, \;i, j \in S_{sub}^t} {{x_{ij}}} \leqslant |S_{sub}^t| - 1, 2 \leqslant |S_{sub}^t| \leqslant |{S^t}| - 2, S_{sub}^t \subseteq \{ 2, ..., |{S^t}|\} , t \in {n_{it}}$

(12)

在上述MRF-SNSA优化问题(2)~优化问题(12)中:

●  约束条件(3)~约束条件(5)保证了在满足RAS之间连通和重叠最小情况下, 形成RAS搜索感知位置. 其中,

  n_it为轮次迭代总数;

  $pCG_{RAS}^t$为第t轮迭代RAS位置集合;

  $|pCG_{RAS}^t|$为第t轮迭代RAS数量;

  Q(i, j)为RAS搜索感知中机器人r_i和r_j间链路质量的二值变量, 且仅当$|pC{G_{{r_i}}} - pC{G_{{r_j}}}| \leqslant {r_c}$时, Q(i, j)=1;否则Q(i, j)=0;

●  约束条件(6)~约束条件(8)保证了第t轮迭代所发现孤岛到BS间至少存在一条有效路由路径, 该路径由前t-1轮迭代已部署的中继集合R^{1, ...,t-1}和当前轮t新部署中继集合R^t组成, 且R^t所承载的网络流数量均不大于K.其中:

  f_ij为中继i对中继j的网络流承载量;

  |f_ij|为中继i对中继j的网络流承载数量;

  $|R_V^{1, \ldots , t - 1}|$为前t-1轮中继集合R^{1, ...,t-1}中, 可由当前轮迭代所利用的中继数量;

●  约束条件(9)~约束条件(12)保证了$m_{RARD}^t$个RARD仅一次遍历${S^t} = \{ R_V^{1, \ldots , t - 1}\} \cup \{ |{R^t}|\} \cup \{ Se{g^t}\} \cup ${RAS^t}中的每个节点, 且其遍历时间与RAS搜索感知时间同步.其中,

  S^t为第t轮RARD所需遍历的节点集合;

  |S^t|为第t轮RARD所需遍历的节点数量;

  f为RARD中继部署的固定消耗;

  c_ij为S^t中任意两个节点i和j的欧氏距离;

  x_ij为二值变量, 当S^t中节点i和j之间的路径隶属于优化结果时, x_ij=1;否则, x_ij=0.

2 MRF-SNSA求解

与文献[8]所提出的SMT-MSP问题一样, MRF-SNSA优化问题(2)~优化问题(12)亦为NP难问题.这是因为如果存在一个解决MRF-SNSA问题的多项式算法, 我们就可以通过令K→∞和$T_{RAS}^t \to \infty $来证明SMT-MSP问题是多项式时间可求解的.显然, 此假设不可能成立.

为了近似求解MRF-SNSA优化问题(2)~优化问题(12), 建立RAS、被发现孤岛以及BS间的路由路径, 实现WSN孤岛间的高效结盟, 我们在连通重叠搜索算法基础上, 以具有带宽约束的中继为部署节点, 以降低其数量为目标, 从提高已部署中继和新部署中继利用率角度出发, 利用层次分簇^[22]和网络流^[23]相关理论, 设计基于搜索带宽感知的层次中继部署算法.

2.1 相关定义

由于每轮RAS搜索感知和RARD中继部署算法一致, 我们以第t轮为例(下文如无特别说明, 均以第t轮为例), 首先将描述基于搜索带宽感知的层次中继部署算法所需的相关定义给出如下:

定义1(动态网络拓扑图).在任意轮次t中, 由RAS^t, Seg^t与BS动态组成的网络拓扑图, 由G(t)={V, E(t)}表示, 其中, V为节点集合, E(t)为节点间无向边集合.

定义2(混合网络拓扑图).在G(t)的无向边集合E(t)之上, 定义并引入RAS^t, Seg^t到BS的有向流集合$\vec E(t)$后, 所形成新网络拓扑图, 由$\bar G(t) = \{ V, E(t) \cup \vec E(t)\} $表示.

定义3(承转源头).在$\bar G(t)$中, 任意节点i∈V已承载且未转发的有向流源头节点集合, 由$V_{ufs}^i$表示, 且:

$V_{ufs}^i \subseteq RA{S^t} \cup Se{g^t}.$

定义4(覆盖网络流).在$\bar G(t)$中, 任意节点i∈V的全部邻接点N(i)的承转源头集合, 由$V_{cf}^i$表示.

定义5(完全覆盖节点).在$ \bar{G}(t) $中, 满足$ V_{ufs}^{N(i)}\subseteq V_{cf}^{i} $的任意节点i∈V的邻接点集合, 由$ V_{fcn}^{i}$表示, 且$ |V_{fcn}^{i}| $表示完全覆盖节点数量.

定义6(层次).按照通信半径大小将每轮结盟过程进行分层, 每一个分层被称为一个层次.其中:有向流源头(无出度)节点集合被作为当前层次, 由current_layer表示; 新部署的中继集合被作为新层次, 由new_layer表示.

定义7(路由序列).在current_layer中, 有向流源头节点i∈V路由到BS所途经的已部署中继序列, 由PathToBS(i)表示.

定义8(承载流量).在current_layer中, 有向流源头节点i∈V所承载网络流数量之和, 由CarriedFlow(i)表示.

定义9(候选边界中继集合).在通信半径R_c范围内, 与当前轮RAS/孤岛距离最小的已部署中继集合R^{1, ..., t-1}的子集, 由$CB{R^t} = \{ CBR_1^t, ..., CBR_i^t, ...\} $表示, 其中, $CBR_i^t$表示任意RAS/孤岛i∈RAS^t∪Seg^t的候选边界中继.

定义10(边界中继集合).在候选边界中继集合CBR^t中, 满足路由序列中所途经节点的承载流量均小于中继带宽K的候选边界中继集合, 由BR^t表示, 且BR^t⊆CBR^t.

2.2 算法实现

在第2.1节中相关定义的基础上, 利用连通重叠搜索算法并结合层次分簇和网络流相关理论, 实现基于搜索带宽感知的层次中继部署算法.

总体步骤如下:

(1) 以RAS移动时间$T_{RAS}^t$为阈值, 从第t轮迭代的边界网格单元集合$C_{frn}^t$中, 利用文献[18]所提出的连通重叠搜索算法, 估算RAS数量$m_{RAS}^t$并对其进行搜索感知, 形成第t轮RAS最优搜索网格单元RAS^t和所发现孤岛代表节点Seg^t, 且相对应位置集合分别为$P_{RAS}^t$和$P_{Seg}^t;$

(2) 对由RAS^t和Seg^t组成混合网络拓扑图$\bar G(t)$, 利用定义6, 形成当前层次current_layer, 并在此基础上, 以欧氏距离为度量标准, 结合定义9, 形成候选边界中继集合$CB{R^t} = \{ CBR_1^t, CBR_2^t, ...\} $, 并以其为簇头集合, 对current_layer中源头节点进行分簇, 形成候选分簇集合$F{N^t} = \{ FN_1^t, FN_2^t, ..., FN_{|CB{R^t}|}^t\} ;$

(3) 针对每个候选分簇, 利用定义3~定义5, 建立簇内源头节点$FN_i^t$与对应簇头节点$CBR_i^t$的最优中继部署, 形成候选中继集合$C{R^t} = \{ CR_1^t, CR_2^t, ..., CR_{|CB{R^t}|}^t\} $, 并在此基础上, 结合定义7、定义8和定义10, 形成其上的候选中继路由序列$pathToBS(1, ..., |CR_i^t|);$

(4) 根据$pathToBS(1, ..., |CR_i^t|)$, 更新并判断每个候选边界中继路由序列$pathToBS(CBR_i^t)$上的节点承载流量:如果$\forall j \in pathToBS(CBR_i^t)$均满足carriedFlow(j)≤K, 那么将其添加到BR^t中, 同时将与其对应的簇内候选中继添加到R^t中, 并跳至步骤(5);否则, 返回执行步骤(3), 重新建立$CBR_i^t$到BS的最优中继部署, 同时将其加入到R^t中, 并跳至步骤(5);

(5) 重复上述步骤(3)和步骤(4), 直至候选分簇集合FN^t为空.

上述步骤(3)作为实现基于搜索带宽感知的层次中继部署算法的关键, 涉及到多个定义的特化以及RARD中继部署、路由建立、冗余归约等过程, 对提高MRF-SNSA问题的求解效率起到了决定性的作用.鉴于此, 我们在第2.1节混合网络拓扑图相关定义的基础上, 以第t轮任意分簇为部署对象, 详细阐述其实现步骤, 并给出其伪代码描述和过程图示.具体如下.

① 参数初始配置

将分簇的簇头节点位置$subP_{CBR}^t$以及其相应的簇内节点位置集合$subP_{CRAS\& Seg}^t$清空; 将$subP_{CRAS\& Seg}^t$置为current_layer层次, 并初始化该层次中每一个节点i的承转源头$V_{ufs}^i$、覆盖网络流$V_{cf}^i$以及完全覆盖节点$V_{fcn}^i$;

② 中继部署及路由建立

首先, 计算current_layer中与$subP_{CBR}^t$距离大于R_c的每一节点i的完全覆盖流数量$|V_{fcn}^i|$, 并按照由大到小的顺序将其保存到ch(如$|V_{fcn}^i|$相同, 则选择距离$subP_{CBR}^t$最小的节点); 然后, 在顺序地从ch中读取每一节点ch(i)的同时, 在ch(i)与$subP_{CBR}^t$之间部署新中继, 并对其完全覆盖范围内的网络流进行聚集; 最后, 将新部署的中继添加到new_layer, 并更新ch及其有向流源头节点到$subP_{CBR}^t$的路由路径;

③ 冗余中继归约

对new_layer中的每一个节点i, 按照完全覆盖流数量$|V_{fcn}^i|$由大到小地进行网络流聚集(如$|V_{fcn}^i|$相同, 则选择最大的覆盖流, 即源头节点数量$|V_{ufs}^i|$), 并同时将new_layer中父节点网络流可以被节点i所聚集的冗余中继删除;

④ 终止判定

将new_layer置为current_layer, 当其中每一节点到$subP_{CBR}^t$的距离均不大于R_c时, 步骤结束; 否则, 计算其上每一节点i的$V_{ufs}^i, V_{cf}^i$和$V_{fcn}^i$, 并跳至步骤②.

上述步骤①~步骤④的伪代码描述见算法1.

算法1.

输入:第t轮任意分簇簇头位置$subP_{CBR}^t$; 簇内节点位置集合$subP_{CRAS\& Seg}^t$; 通信半径R_c; 中继带宽约束K;

输出:从簇内节点到簇头所需部署的新中继位置集合$subP_R^t$、所承载网络流量集合subCarriedFlow^t以及路由路径集合$subP_L^t$.

1  $subP_R^t \leftarrow null;{\rm{ }}subCarriedFlo{w^t} \leftarrow null;{\rm{ }}subR_L^t \leftarrow null;$

2  $current\_layer \leftarrow subP_{CRAS\& Seg}^t$; new_layer←null;

3  计算current_layer中每一节点i的$V_{ufs}^{i}, V_{cf}^{i} $和$ V_{fcn}^{i}; $

4  while $ dist(\exists \ current\_layer(i), subP_{CBR}^{t})>{{R}_{c}} $ do

5    ch←current_layer;

6    while ch≠null do

7      从ch中选择具有最大$V_{fcn}^i$的ch(i);

8      new_layer←new_layer∪根据ch(i)与$subP_{CBR}^t$的距离, 部署新中继;

9      for j←1 to K

10        $subR_{L}^{t}\leftarrow subR_{L}^{t}\cup \{V_{fcn}^{ch(i)}(j),\ ch(i)\};\text{ }subP_{R}^{t}\leftarrow subP_{R}^{t}\cup new\_layer;$

11    end for

12    $ch\leftarrow ch\backslash (V_{fcn}^{ch(i)}\cup \{ch(i)\})$, 并重新计算ch中每一节点i的$ V_{ufs}^{i}, V_{cf}^{i} $和$ V_{fcn}^{i}; $

13  end while

14  ch←new_layer, 并计算ch中每一个节点i的$V_{ufs}^{i}, V_{cf}^{i}$和$ V_{fcn}^{i}; $

15  while ch≠null do

16    从ch中选择具有最大$V_{fcn}^i$的ch(i), 并对其网络流进行聚集;

17    if ∃ch(j) and $ |V_{ufs}^{ch(j).parent}|=0 $

18      ch←ch\{ch(j)}, 并更新$ subP_{R}^{t} $和$subP_{L}^{t}$;

19    end if

20    重新计算ch中每一节点i的$ V_{ufs}^{i}, V_{cf}^{i}$和$ V_{fcn}^{i}; $

21    $ subCarriedFlo{{w}^{t}}\leftarrow subCarriedFlo{{w}^{t}}\cup V_{fcn}^{i}; $

22  end while

23  current_layer←new_layer; new_layer←null;

24 end while

25 return $ subP_{R}^{t}, subCarriedFlow_{R}^{t}, subR{{L}^{t}};$

由上述步骤可知, 算法1以中继部署及路由建立和冗余中继归约为主体, 通过主体间循环嵌套方式, 实现各分簇的中继部署.其中,

●  主体间循环嵌套次数为m;

●  中继部署及路由建立的伪代码位于算法1的第4行~第14行, 其时间复杂度为$O(|subR_L^t| \cdot |ch| \cdot |K|), $其中, $|subR_L^t|$为最优分簇数量, 由文献[16]可知, 其与$\sqrt n $成正比; |ch|为当前层次的节点数量, 即|ch|≤n; K为中继带宽常数.因此在最坏情况下, 该部分的时间复杂度为O(n²);

●  冗余中继归约的伪代码位于算法1的第15行~第22行, 其时间复杂度为O(n).

综上所述, 在最坏情况下, 算法1的时间复杂度为O(mn²).

此外, 我们还给出了一个过程图示, 其中, 图 3(a)为簇头及其簇内节点初始位置, 且从其余几幅图示中可以看到:整个中继部署过程存在3个层次, 而每一层次都需要执行一遍上述步骤①~步骤④.然而, 由于第1层次图 3(b)和第3层次图 3(f)不存在冗余中继, 即不需要冗余中继归约步骤.为了不失一般性, 我们仅对包括冗余中继归约步骤的第2层中继部署图 3(c)~图 3(e)进行详细说明, 其中,

●  图 3(c)为中继部署及路由建立过程:由current_layer={1, 2, 3, 4, 5, 6}以及$V_{fcn}^{current\_layer} = \{ 1, \;2, \;1, \;1, \;1, \;2\} $可知, 中继2和中继6具有相同的最大完全覆盖节点数量, 但因中继6距离BR较远且处于中继2的完全覆盖范围之内, 故优先对中继2进行网络流聚集, 即中继2聚集中继6的全部网络流, 并在其与BR之间部署新中继7, 同时将{7, 2}添加到$R_L^t$中.对于current_layer中除2之外的其他中继, 以同样的方式进行数据流聚集, 并部署新中继8~中继11, 同时更新$R_L^t, $形成下一层次new_layer={7, 8, 9, 10, 11};

●  图 3(d)、图 3(e)为冗余中继归约过程:由$V_{fcn}^{new\_layer} = \{ 1, \;1, \;2, \;1, \;2\} $可知, 中继9和中继11具有相同的最大完全覆盖节点数量, 但因$|V_{ufs}^{11}| = 1$小于$|V_{ufs}^9| = 2, $故优先对中继9进行网络流聚集.此时, 处于中继9完全覆盖范围内的中继8的全部网络流可被吸收, 即$|V_{fcn}^8| = 0, $故中继8是冗余中继, 可从new_layer中删除. 按照同样的方式, 中继11可以对其完全覆盖范围内的父中继3进行网络流聚集, 但此聚集并不会导致$|V_{fcn}^9| = 0, $故不会产生冗余中继.以此类推, 分别归约剩余中继, 形成中继冗余归约后的新层次:

$ new\_layer=\left\{ 7,9,10,11 \right\}. $

3 性能评估 3.1 仿真对比实验

为了评估MRF-SNSA的性能, 我们在不同的中继通信半径R_c、中继带宽K、孤岛数量N_Seg和感知区域A下, 以中继部署数量和中继部署时间为评价指标, 以MATLAB为仿真平台, 将所提出的MRF-SNSA与OBiC^[14], CRAFT^[11]和SMT-MSP^[8]进行对比仿真实验.仿真环境和初始条件设置如下:①网络由1 200个随机部署于感知区域A内的传感器节点和1个BS组成, 且BS位于A的中心位置; ②传感器节点的感知与通信半径分别为7m和10m;③ 20个机器人初始化于感知区域A的中心位置, 且其移动速度v=3m/s, T_d=T_sti=2s;④机器人的感知与通信半径分别14m和20m;⑤中继为普通的传感器节点, 且其带宽K=4.此外, 考虑到网络拓扑的随机性, 图中每一数据点均为100次仿真实验结果的平均值.

3.1.1 中继部署数量

图 4给出了随着中继通信半径R_c、中继带宽K、孤岛数量N_Seg和感知区域A逐渐增加, MRF-SNSA与ObiC, CRAFT和SMT-MSP在中继部署数量上的对比结果.

图 4(a)中, 在K=4, N_Seg=5, A=1000m×1000m下, 随着R_c的增加, MRF-SNSA与对比方法的中继部署数量均逐渐减少.这是因为中继部署数量由孤岛间路由跳数决定, 而其恰与R_c成反比.此外, 与对比方法相比, MRF-SNSA的优势更为突出.这是因为MRF-SNSA在部署新中继时充分地利用了已部署中继的剩余带宽, 更为高效地降低了中继数量.图 4(b)中, 在R_c=60, N_Seg=5, A=1000m×1000m下, 随着K的增加, MRF-SNSA与对比方法的中继部署数量均逐渐减少.这是因为中继带宽K的增加, 使其能够聚集更多孤岛流量, 间接地提高了已部署中继的利用率, 继而降低了所需部署的新中继数量.图 4(c)中, 在R_c=60, K=4, A=1000m×1000m下, 随着N_Seg的增加, MRF-SNSA与对比方法的中继部署数量均逐渐增加.这是因为孤岛数量与网络总流量成正比, 而更多的流量需要部署更多的中继来承载.值得注意的是:同一区域的孤岛密度会随着N_Seg的增长而增加, 这使得MRF-SNSA和OBiC有更多机会利用已部署的中继剩余带宽, 故而中继部署数量的增加较为缓慢.相比之下, CRAFT和SMT-MSP的中继部署数量会急剧递增.这是因为他们在孤岛间的最短路径上部署中继, 而随着N_Seg的增加, 最短路径增多, 继而导致中继部署数量剧增.图 4(d)中, 在R_c=60, K=4, N_Seg=5下, 随着A的增加, MRF-SNSA与对比方法的中继部署数量均逐渐增加.这是因为孤岛间距与感知区域成正比, 故而随着感知区域增长, 结盟孤岛需要部署更多中继.值得注意的是:当A≤1100m×1100m时, SMT-MSP的中继部署数量甚至比CRAFT的更少.这是因为在一棵最小生成树上所需部署中继的数量要低于孤岛间直接中继部署数量, 且此情况在感知区域较小时更为显著.

3.1.2 中继部署时间

图 5给出了随着中继通信半径R_c、中继带宽K、孤岛数量N_Seg和感知区域A逐渐增加, MRF-SNSA与OBiC、CRAFT和SMT-MSP在中继部署时间上的对比结果.

图 5(a)中, 在K=4, N_Seg=5, A=1000m×1000m下, 随着R_c的增加, MRF-SNSA与对比方法的中继部署时间均逐渐降低, 且与图 5(a)中继部署数量降低趋势十分相似.这是因为由搜索带宽感知模型(1)可知, RARD中继部署时间与T_d和$T_{RARD}^t$成正比, 而其中$T_{RARD}^t$由中继分布和机器人移动速度决定.在本文对比方法中, 均利用树相关理论形成中继位置, 因此其分布相对一致.故在机器人移动速度相同的情况下, 各方法中继部署时间主要由中继数量决定.图 5(b)~图 5(d)分别给出了随着中继带宽K、孤岛数量N_Seg和感知区域A逐渐增加, MRF-SNSA与ObiC, CRAFT和SMT-MSP在中继部署时间上的对比结果.值得注意的是:图 5(b)~图 5(d)分别与图 4(b)~图 4(d)中继部署数量降低趋势相似, 其主要原因已在图 5(a)的实验分析部分给出.此外, 图 5(b)中, 在R_c=60, N_Seg=5, A=1000m× 1000m下, 随着中继带宽K增加到6之后, MRF-SNSA和OBiC的中继部署时间处于缓慢下降状态, 而CRAFT和SMT-MSP的中继部署时间基本停滞.这是因为中继带宽K的进一步增加并没有导致孤岛间距离的变化, 而距离在CRAFT和SMT-MSP孤岛结盟过程中起决定性作用.相对之下, 随着中继带宽K的进一步增长, 虽然中继所承受的网络流量也在放缓, 但中继数量仍有下降趋势.图 5(c)中, 在R_c=60, K=4, A=1000m×1000m下, 随着N_Seg增加, 结盟孤岛所需的网络流数量呈指数递增, 此时需要消耗更多的中继部署时间来部署中继.值得注意的是, 当孤岛数量N_Seg < 5时, MRF-SNSA的中继部署时间要高于ObiC, CRAFT.这是因为在所需部署的中继数量较低时, 具有较低复杂度的OBiC和CRAFT对中继部署时间的影响更为明显.图 5(d)中, 在R_c=60, K=4, N_Seg=5下, 当感知区域的边界长度小于900m时, CRAFT, MRF-SNSA和OBiC的中继部署时间逐渐增加, 而SMT-MSP的中继部署时间仅出现微小增加, 且在此过程中, CRAFT与OBiC的中继部署时间十分接近.这是因为感知区域A越小, 已部署中继的利用率就越高, 所需部署的新中继数量就越少.故相比于较大感知区域时, 各方法的时间复杂度对中继部署时间的影响更加显著.

3.2 实际对比实验

由于实际设备和场地的限制, 无法模拟出仿真对比实验的无线传感器网络规模, 仅选取东校区第一运动场作为监测区域, 面积为90m×90m.在该监测区域中, 随机部署50个GreenOrbs GF-103S型太阳能驱动全天候传感器节点, 通信半径为15m.2台xPartner IN-RT四轮野外机器人初始部署于监测区域中心, 移动速度为1m/s.BS为GM-320E型Mesh通信节点, 部署于监测区域边界.所需部署的中继为普通传感器节点(GF-103S型), 且其容量K可动态调整.实际对比实验场景如图 6所示.此外, 为了降低由硬件数量、性能等诸多因素带来的偶然误差, 取100次独立实验数据的平均值作为最终结果.

由优化问题(2)~优化问题(12)可知, 提高中继带宽约束下WSN孤岛结盟效率的关键在于控制新部署中继数量.虽然第3.1节的仿真对比实验已经较为完整地分析和验证了所提出MRF-SNSA的有效性, 但其不够直观形象, 故本节以实验室现有硬件为基础, 以穷举式蛮力算法(optimality)^[24]的最优中继部署数量为参考, 搭建上述实际环境测试场景, 并在仅考虑中继带宽约束下, 直接地给出各方法中继部署数量与最优中继部署数量的实际对比实验.结果及分析如下:

如图 7所示, 随着中继带宽K的逐渐增加, MRF-SNSA与ObiC, CRAFT和SMT-MSP的中继部署数量均逐渐降低, 且MRF-SNSA明显优于上述对比方法.此外, 由于MRF-SNSA以簇为单位进行局部结盟, 故其中继部署数量无法达到Optimality算法的全局优化结果, 但其已然十分接近于该结果.值得注意的是:与CRAFT相比, OBiC的中继部署数量更接近于MRF-SNSA.这是因为其以最小生成树为中继部署路径约束, 有效地延缓了中继部署数量的增长比率.

4 结论

孤岛结盟是无线传感器网络拓展自身应用领域和提高资源受限环境下应急响应速度的关键.我们在这方面进行了有益的探索和尝试, 引入了同步轮次流水迭代过程, 构建了MRF-SNSA优化问题, 并在此基础上设计了一种基于搜索带宽感知的层次中继部署算法.通过与现有方法进行对比实验, 结果表明:MRF-SNSA能够在满足中继带宽约束下, 以孤岛搜索与中继部署同步的轮次流水迭代方式, 最小化中继部署数量, 高效地实现未知环境的孤岛结盟.