刘文军,王 喜,林政宽

(1.苏州工业职业技术学院软件与服务外包学院,江苏 苏州 215104;2.苏州大学计算机科学与技术学院,江苏 苏州 215006)

嵌入式系统和无线通信技术的进步催生了无线传感器网络WSNs(Wireless Sensor Networks)的产生。由于传感节点传输范围有限,WSNs通常采用多跳通信,这使得对大规模区域的监测成为可能。近几年的研究成果表明,在WSNs中引入移动元素MEs(Mobile Elements)可以有效解决传统WSNs面临的能效等问题,并且能够有效降低成本、提高系统的可靠性[1-6]。

当前数据收集模式中采用移动数据收集器MDC(Mobile Data Collector)访问网络中的所有传感节点能够最大化能量效率,然而由于MDC移动速度有限,当网络规模较大时,该模式面临显著的时延瓶颈。为了解决该问题,基于Rendezvous的移动数据收集模式成为一种高效的替代方法[7-12]。在该模式中,传感区域中的一个节点子集首先基于某种策略被选为集结点RPs(Rendezvous Points)。数据传输过程中,节点从其附属节点汇聚局部数据,由其缓存并等待移动数据收集器到达时上载数据。值得注意的是从传感节点到RP之间的传输跳数应当加以限制[9,13]。首先,WSNs的固有特征要求高的能量效率。采用多跳中继数据容易因漏斗效应导致传感节点间能量消耗不平衡,特别是跳数过多时愈发明显。第二,中继跳数过大意味着RP节点应当具有强的节点性能,因为在MDC到达前这些节点应当有足够的存储空间来缓存和处理数据。这对能量和功能受限的传感节点来说是不切实际的。最后,诸如实时监测之类的应用往往对时延要求苛刻,而中继跳数过大或无法预测均不能很好地满足该需要。

1 问题定义

1.1 网络模型

在基于Rendezvous 的无线传感器网络数据收集应用中,源节点产生的数据需要被持续不断地发送到RP进行缓存,等待MDC近距离进行收集,因此需要确立数据汇聚的路由和MDC的移动轨迹。

无线传感器网络通过无向图G(V,E)来模拟,其中顶点集V表示所有传感节点,边集E表示连接相邻节点的通信链路。V中的两个顶点u和v是相邻的当且仅当它们在彼此的通信范围内,称u是v的邻居,反之亦然。图G中的一条路径P=p(v1,vl)=是l个不相同顶点的序列,使得任意两个连续的顶点是相邻的,其长度 |P|=l-1(l>1)。u,v之间的最短路径的长度叫做u,v间的距离,记作d(u,v)。网络G的直径是指任意两个节点间距离的最大值,记为dG。顶点v的邻居是所有G中与v相邻的所有顶点集,记为N(v)。对任意的v∈V和一个非负整数k,v的k跳邻居定义为k-NG(v)(简记为k-N(v)),按照惯例,0-NG(v)={v}。

基于潜在通信拓扑G,通过一个有向汇聚树的集合T={Ti}来表示数据收集应用中实际的数据传输路由。对任意的一棵路由树Ti(0

为了研究问题的方便,在参考现有文献的基础上,我们对传感节点和潜在网络模型作出以下假定:

①假定N个同质的传感节点随机分布于规则的传感区域,不考虑障碍物影响,在确定的通信半径下所有通信链路都是对称的。

②MDC位于网络中的某处以可控制性移动模式移动在网络中漫游。MDC资源和功能均不受限制。

③传感节点首先通过有限跳通信将数据传递到选出的支配节点DNs(Dominating Nodes)进行缓存,假定普通传感节点的存储容量足够大,从而在被确定为DN后能够在MDC到达前缓存附属节点产生的数据。仅当MDC停留在任一DN通信范围内请求数据上载,传感节点启动数据传输。

④假定MDC装备有全球定位系统GPS(Global Positioning System)单元或其他位置服务模块,从而能够确定自身的物理位置。出于一般性考虑,普通传感节点不具备以上功能。

⑤沿着多跳路径传输一个数据包的总能量消耗与发送者和接受者之间的欧氏距离成比例。

1.2 问题定义

本文MDC最小延迟轨道规划问题的解决主要基于k跳支配集的构建,以支配节点DNs充当RP,因而首先正式给出k跳支配集的概念。

定义1图G(V,E)的一个k跳支配集是一个子集D⊆V,满足对于VD中的任意一个顶点v,存在某个顶点u∈D,使得从v到该顶点的距离至多为k。

基于Rendezvous模式的移动数据收集问题中,MDC从初始位置启动每次数据收集过程,MDC在遍历所有RN后最终返回到初始位置。支配节点确定了MDC行进轨道的锚点,在MDC速度保持不变的情况下,轨道长度决定了数据收集的时延。问题的需求是在k跳支配约束下MDC移动轨迹长度尽可能短,以达到缩短数据收集时延的目的。该问题中MDC 的路径规划和以支配节点为根的汇聚树中的路由需要联合进行考虑以寻找到整体最优解。我们称该问题为基于k跳支配集的MDC最小时延规划问题MLP-kDS(Minimum Latency Planning of MDC based onk-hop Dominating Sets),并将其定义如下:

定义2给定一个传感节点集合S={s1,s2,…,sN} 和中继跳约束k,在网络G中寻找一个连接π和D中所有节点的MDC的轨道U,要求满足如下条件:

D2-1 一个最小规模的k-DS集合D,其分布尽可能靠近MDC的初始位置π;

D2-2 ∑(u,v)∈ U|uv|是最小的,其中(u,v)是轨道U上的路线,|uv|表示其欧式距离;

D2-3 一个以D中节点为根高度至多为k的汇聚树集合T={Ti(Vi,Ei)},使得UiVi=S且∑i∑(u,v)∈ Ei|uv|最小。

从定义可见,以获得尽可能短的MDC轨道为目标,DN的个数与分布、访问次序、以及每棵特定的以DN为根满足中继跳限约束的汇聚树形态分别通过条件 D2-1,D2-2和D2-3 给出,求解时应联合加以考虑。对V中任意的r和v,如果存在一条从v到r的路径,则称顶点v被顶点r覆盖。如果该路径的长度为k,则称顶点v是由r所k跳覆盖的。实际上,网络中的一个传感节点集合被r所覆盖意味着产生了一棵从这些节点收集信息并汇聚到根节点r的数据汇聚树。k跳覆盖保证了来自任意数据源的数据包在不超过k个中继跳被发送到r。参数k的设置取决于用户的需求,反映了能量效率和数据收集时延之间的平衡。

定理1MLP-kDS问题是NP难的。

证明MLP-kDS 问题包含3个相关条件。Amis等证明单位圆盘图最小k跳支配集是NP完全的[14]。以下证明即便不考虑k-DSs的规模,最短MDC轨迹问题仍然是NP难的,这可以通过从一个给定的欧氏旅行售货商问题TSP(Traveling Salesman Problem)的多项式时间归约到问题的一个特例来证明。给定一个网络G=(V,E)作为TSP问题的实例。条件 D2-2 决议版的一个特例是判定是否存在一个DN的集合包含网络中的所有节点。这可以通过调整节点的通信范围Rt完成。当Rt足够小,节点相互间均是不可达的。此时,中继跳数k恰好等于0,MDC必须访问所有的传感节点来收集数据。该情况下意味着所有节点都是DN。这恰好是一般的旅行售货商问题。所以MLP-kDS是NP难的。

2 k-DDSR算法

2.1 分布式算法设计

由于MLP-kDS问题是NP 难的,本节给出一个分布式的k跳DN确定算法k-DDSR(Distributedk-hop Dominating Sets and Routing)来解决定义的问题。算法的主要思想是首先构建网络G的k-跳支配集以及每个成员节点所附属的支配节点,后者构成通信时的路由树。所构建的支配节点应满足如下条件:支配节点的规模|D|尽可能小、负载尽可能均衡、位置尽可能靠近MDC初始位置,从而使得最终生成的MDC的轨迹长度尽可能短。

定义3网络中给定以r为根的路由树Ti,若从当前节点si到祖先节点sj的距离为d,即dist(si,sj)=d,则称节点sj是Ti中si的d父节点,记为d-PN。

给定通信范围Rt下的网络G(V,E)、MDC初始位置π和跳限参数k,由任意传感节点si执行的分布式的k跳支配集D和路由树集T构建算法过程如图1所示。

图1 k-DDSR算法流程图

Step 1 节点标识符分配 初始时每个节点依据信号强度按照距离MDC起始位置π的距离分配一个ID,距离π越远得到的ID越大,反之,ID越小。

Step 2 节点状态及路由确定 如果当前节点si的距离标识符大于所有邻居的标识符,则节点si变为成员节点状态,记为“MN”,si记录ID号最小的邻居为其路由树的d-PN,d≤k,并从原网络中剪除与之关联的其他通信边/链路。

特别地,如果si与其状态未确定邻居构成局部全连接网络(任意两个节点都存在通信边),且si∪N(si)比其邻居的ID更大,则除了ID号最小的邻居外均变为“MN”,si记录ID号最小的邻居为其路由树的1-PN。

Step 3 通过k-PN迭代确定DN 重复Step 2至多k次。每次迭代过程中,如果si自身为i-PN,则si选择的新父节点记为(i+1)-PN,si本身变为成员节点。不足k次,则该节点确定自身状态为DN,终止循环。

对Step 3确定的网络中的k-PN,令其状态为DN。

Step 4 通过消息转发确定DN所属成员及路由 所有DN向k跳范围内尚未确定父节点的邻居发送(转发)DN声明消息DEC_MSG(ID,r,i),最先收到该消息的i-PN或状态未确定的节点变为DN的成员节点,记录自身的i-PN,并从网络中剪除到ID比自身大的通信边。DEC_MSG消息至多传输k跳后结束,此时形成第1批k跳支配节点及受其支配的成员节点。

Step 5 算法迭代确定所有节点状态及路由 对网络中所有状态未确定的节点,继续执行Step2～Step4,直至每个节点要么是“MN”,要么是“DN”。特别地,对不连通网络会同时运行上述算法。

以下通过图2举例说明当k=2时算法的执行情况:图2(a)给出了29个节点和一个MDC及其初始位置π时的网络配置情况。其中,节点旁边的数字为依据位置π生成的距离标识符。假定节点的状态用不同的颜色匹配,其中“MN”(灰色节点),“DN”(黑色节点),“UN”(白色节点)。初始时所有节点状态均为“UN”。图2(b)给出算法执行第1轮中确定首批成员节点的情形。图2(c)给出算法执行第1轮中确定第2批成员节点的情形,其中节点6、7、12、14组成2-PN,充当DN并向网络中的2跳邻居发送DN声明消息来招募成员。接收到消息的节点,包括状态未确定的节点及1-PN,选择加入距离最近的DN,自身变为成员节点。最后,图2(d)给出最终的DN、MN和按照贪心算法生成的MDC轨迹。从图2可以看出,对于一个由27个节点构成的网络,算法仅执行一轮即可构建出中继跳数为2的支配节点和相应的路由树,表明了所提出的分布式算法的高效性。

图2 k-DDSR算法执行示例

2.2 MDC轨迹长度

给定k-DS的集合D和初始位置π,以下步骤给出求解MDC轨迹U的过程。

Step 1 基于确定的k-DS集合D,通过Prim算法构建以π为根的MSTTR。

Step 2 对TR应用Christofides 1.5-近似算法[15]生成解U。

采用Prim算法求解TR时间复杂度为O(|D|2)。基于TR采用Christofides 1.5-近似算法产生U的时间复杂度为O(|D|3+N),此处|D|和N分别为k-DS的规模和网络规模。

3 算法效率分析

本节分析k-DDSR算法的执行效率,首先给出正确性证明,然后给出k跳支配集的规模,最后呈现时间和消息复杂度分析。

定理2k-DDSR算法执行结束后,任意节点要么是支配节点,要么是成员节点且该节点到支配节点的路由跳数不超过k。

证明算法的正确正确执行由算法中的两个关键步骤保证:一个是成员节点的确定(Step 2);另一个是k-PN的确定(Step3),分为正常结束和提前终止操作步骤两种情况。其中“k-PN”保证DN对MN的k跳覆盖。被确定为k-PN的支配节点总是从局部最远节点到当前节点的路由跳数为k,然后k-PN向其k跳邻居发送声明消息;“提前终止”保证当网络规模相对较小时仍能够选出DN,对成员节点进行支配,从而保证算法正常结束。

定理3给定网络规模为N直径为dG的连通无线传感器网络G,k-DS的规模满足 |D|≤⎣N/(k+1)」,1≤k≤dG。

证明:算法一次迭代后确定i-PN,分为两种情况:

情况1i

情况2i=k任意标记为k-PN的节点y向其k跳邻居k-NG(y)发送DN声明消息。最坏情况下,无新的DN生成,因此每个支配节点仅包含k个成员节点,如图3(b)所示。

综上,两种情况下k-DS的规模满足 |D|≤⎣N/(k+1)」。

图3 k-DDSR算法证明

定理4给定规模为N的无线传感器网络G,采用k-DDSR算法确定k-DS和数据汇聚树集T所需的最坏时间复杂度为O(dG/k),其中dG为网络直径。

证明算法以迭代方式运行,迭代过程中随着节点状态的确定节点不断从原网络中剪除,从而网络的规模(直径)逐渐变小,直至为1。

节点仅知道其直接邻居信息,在每次迭代中,节点首先确定其临时父节点(i-PN),自身状态变为“MN”,当循环执行完毕,k-PN发送DN声明消息,成员节点加入相应的支配节点,该过程需要O(k)时间。因而,在一次循环中所需要的时间复杂度为O(2k)。

最坏情况下,当MDC位于网络的边缘,此时算法迭代从网络的最远端开始。由于每次迭代花费的时间为O(2k),共需要迭代次数为dG/2k,因而总的时间花费为O(dG/k)。

定理5给定中继跳限为k的无线传感器网络G,采用k-DDSR算法解决MLP-kDS问题时每个节点的消息交换复杂度为O(1)。

证明网络中确定的任意一个支配节点首先向其除孩子节点外的直接邻居发送DN声明消息,消息在网络中至多传播k跳。网络中任一节点收到来自不同节点发送的DEC_MSG消息,仅记录首先收到的节点为父节点,并转发给其余邻居,后续收到的声明消息被丢弃。

算法依次方法迭代,网络中的每个节点最多只收到一次声明消息和转发一次声明消息,因此消息交换复杂度为O(1)。

4 系统仿真

4.1 仿真设定

前文中给出了解决MLP-kDS问题的分布式算法其性能分析。本节通过仿真实验对所提出的算法进行性能评估,并呈现仿真结论。仿真采用Java语言实现,选择一台2核8G内存台式机上进行,仿真参数设置如表1所示。

表1 参数设置

网络时延主要包括节点到DN的路由时间和MDC以一定速度遍历所有DN的时间两个方面。由于数据路由时间可以忽略,因而主要考察后者引起的时延。仿真关注的性能量度主要包括:

①DN的数目(NDN)。在中继跳数确定下,DN的数目直接影响MDC的轨迹长度。节点数目越多,MDC遍历所有DN节点所生成的移动轨迹越长。

②MDC轨迹长度(LMDC)。在MDC移动速度确定下,遍历所有MDC花费的时间可以映射为轨迹长度。

仿真中通过变换节点通信范围Rt,中继跳限k,网络规模N等参数来评估算法的性能,将其与当前类似的移动数据收集算法PB-PSA[9],AT-DRDA[12]和TRACK[16]进行性能比较。TRACK 为基于连通支配集的汇点移动数据收集模型。PB-PSA和AT-DRDA算法均用于解决中继跳数约束的MDC数据收集问题,其中 PB-PSA 以分布式方式获得理想的集结点,该算法采用了两个参数用来指导RP的选择过程,一个参数是当前节点的d跳邻居个数,另一个参数为当前节点到数据汇点的最小跳数。分布式的AT-DRDA算法基于最短路径树以迭代方式确定RP。

4.2 仿真结论

仿真中,我们考虑一个具有N个节点随机分布于200 m×200 m正方形区域的传感器网络,MDC的位置处于传感区域的中心。在MDC到达各节点前每个数据包在中继跳限k的约束下局部地汇聚到DN上进行缓存。仿真过程中我们采用最近邻居NN(Nearest Neighbor)算法[17]来产生MDC的移动轨迹。考虑网络拓扑的随机性,尽可能最小化性能误差,图中的每个性能点是对100次试验取平均值获得的结果。

以下给出不同网络规模下算法k-DDSR与TRACK、PB-PSA 和 AT-DRDA的性能对比。参数Rt和k分布设为30 m和2。评估不同网络规模下支配节点的数目(NDN)和MDC轨迹(LMDC)的长度。图4和图5绘制了不同算法随着N从50逐渐增到400过程中的性能对比。对于NDN和N的关系,算法k-DDSR总体上优于其他两种分布式算法。

图4 网络规模N与延迟DN规模的关系

图5 数据传播延迟与MDC移动速度的关系

为了保证MDC的移动轨迹尽可能短,算法中k-DS的选择主要考虑两个因素:一是其位置分布尽可能逼近MDC的初始位置π,另外保证其规模尽可能小。在确定的中继跳限k,如果MDC的平均移动速度不变,则轨迹长度越小,意味着数据收集的间延迟越短。因此,图4中较小的NDN规模对应图5中更短的MDC移动轨迹。当节点规模为400时,分别比AT-DRDA、PB-PSA和TRACK算法生成轨迹长度降低10.2%、14.3%、20.1%。

5 结论

本文研究了基于Rendezvous模式的移动数据收集轨道规划问题MLP-kDS及其形式化定义。基于k跳支配集给出了k-DS节点分布式构建算法k-DDSR。算法的主要思想是针对无线传感器网络特征以分布式方式从网络边缘向中心迭代确定集结点,并且联合考虑MDC的轨迹和数据汇聚树的路由。所提出算法的效果通过理论分析和仿真实验进行评估,理论上证明了算法的正确性,并给出了k-DS 的规模界以及时间和消息交换复杂度。仿真实验表明,相比同类算法AT-DRDA,MDC的轨迹长度缩短了10.2%。