景 荣,孔令富,赵逢达,练秋生

1(燕山大学 信息科学与工程学院,河北 秦皇岛 066004)

2(河北省计算机虚拟技术与系统集成重点实验室(燕山大学),河北 秦皇岛 066004)

通讯作者:景荣,E-mail:jingrong@ysu.edu.cn

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

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

Fig.1 Islanding (disjoint segments)effect in WSN图1 网络孤岛效应

现有的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={s1,s2,...,sn}是感知区域A内的所有节点集合,E是连接节点间边的集合.此外,节点具有相同的最大感知半径Rs和通信半径Rc,且可通过定位算法获知自身位置.

(2)机器人模型

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

(3)孤岛模型

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

(4)环境模型

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

(5)拓扑模型

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

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

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

1.2 问题公式化

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

Table 1 Symbols and definitions表1 符号及定义

Fig.2 Iterative process of synchronizing the step-flow rounding图2 同步轮次流水迭代过程

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

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

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

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

· 目标函数:

· 约束条件:

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

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

其中,

➢nit为轮次迭代总数;

➢Q(i,j)为RAS 搜索感知中机器人ri和rj间链路质量的二值变量,且仅当时,Q(i,j)=1;否则Q(i,j)=0;

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

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

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

➢St为第t轮RARD 所需遍历的节点集合;

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

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

➢cij为St中任意两个节点i和j的欧氏距离;

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

2 MRF-SNSA 求解

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

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

2.1 相关定义

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

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

定义2(混合网络拓扑图).在G(t)的无向边集合E(t)之上,定义并引入RASt,Segt到BS 的有向流集合后,所形成新网络拓扑图,由表示.

定义3(承转源头).在中,任意节点i∈V已承载且未转发的有向流源头节点集合,由表示,且:

定义4(覆盖网络流).在中,任意节点i∈V的全部邻接点N(i)的承转源头集合,由表示.

定义5(完全覆盖节点).在中,满足的任意节点i∈V的邻接点集合,由表示,且表示完全覆盖节点数量.

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

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

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

定义9(候选边界中继集合).在通信半径Rc范围内,与当前轮RAS/孤岛距离最小的已部署中继集合R1,...,t-1的子集,由表示,其中,表示任意RAS/孤岛i∈RASt∪Segt的候选边界中继.

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

2.2 算法实现

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

总体步骤如下:

(2)对由RASt和Segt组成混合网络拓扑图,利用定义6,形成当前层次current_layer,并在此基础上,以欧氏距离为度量标准,结合定义9,形成候选边界中继集合,并以其为簇头集合,对current_layer中源头节点进行分簇,形成候选分簇集合;

(3)针对每个候选分簇,利用定义3～定义5,建立簇内源头节点与对应簇头节点的最优中继部署,形成候选中继集合,并在此基础上,结合定义7、定义8 和定义10,形成其上的候选中继路由序列;

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

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

①参数初始配置

②中继部署及路由建立

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

③冗余中继归约

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

④终止判定

将new_layer置为current_layer,当其中每一节点到的距离均不大于Rc时,步骤结束;否则,计算其上每一节点i的,并跳至步骤 ②.

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

算法1.

输入:第t轮任意分簇簇头位置;簇内节点位置集合;通信半径Rc;中继带宽约束K;

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

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

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

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

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

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

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

Fig.3 Schematic diagram of relay hierarchical deployment within the cluster (t-round,K=4)图3 簇内层次中继部署示意图(第t 轮,K=4)

3 性能评估

3.1 仿真对比实验

为了评估MRF-SNSA 的性能,我们在不同的中继通信半径Rc、中继带宽K、孤岛数量NSeg和感知区域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,Td=Tsti=2s;④ 机器人的感知与通信半径分别14m 和20m;⑤ 中继为普通的传感器节点,且其带宽K=4.此外,考虑到网络拓扑的随机性,图中每一数据点均为100 次仿真实验结果的平均值.

3.1.1 中继部署数量

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

Fig.4 Comparison of the number of deployed relays in every algorithm under different network parameters图4 在不同网络参数下各算法的中继部署数量对比

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

3.1.2 中继部署时间

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

Fig.5 Comparison of the relay deployment time in every algorithm under different network parameters图5 在不同网络参数下各算法的中继部署时间对比

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

Fig.6 Test scenarios in a real environment图6 实际环境测试场景

由优化问题(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.这是因为其以最小生成树为中继部署路径约束,有效地延缓了中继部署数量的增长比率.

Fig.7 Comparison of the number of deployed relays in every algorithm and the optimal number of deployed relays under different relay’s bandwidth K图7 在不同中继带宽K 下各算法的中继部署数量与最优部署数量的对比

4 结 论

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