无线传感器网络多天线移动式数据收集算法

辛强伟，唐云凯，许晓婷

（咸阳师范学院 a.计算机学院，b.资源环境与历史文化学院，陕西 咸阳 712000）

无线传感器网络（Wireless Sensor Networks,WSN）中节点通过一跳或多跳的方式将感知数据传送到Sink。关于Sink的研究在数据收集中有着重要地位，其研究主要包括单一Sink、多Sink以及移动Sink等。单一Sink的WSN可能会存在负载不均衡问题[1-3]。多个Sink因为有多路径的分流作用，从而减少或避免了热点节点的出现，且多个Sink可以减少网络平均跳数使节点的能耗降低，从而提高WSN的生存时间[4-8]。

通过多跳将数据传送到位置固定的Sink有一定的局限。首先，对于特大面积的监测区域，需要大量节点，成本较大。第二，野外复杂环境中有些地方不易到达，难以部署节点或及时更换节点电池，从而使WSN不连通，网络分割为若干个连通分支和多个孤立节点。第三，如果采用随机部署节点的方式，当节点部署密度较小时，节点分布有时是不均匀的，有可能存在空洞[9]。如果要避免空洞，则需部署大量节点，但会大幅提高成本[10]。第四，节点电量耗尽、故障以及人为破坏等原因，会使WSN由连通变为非连通，导致不能完成监测任务。移动Sink可以减少所需部署的节点，且能在无人状态下前往环境复杂恶劣的地点，能够在WSN非连通的情况下通过自身的移动收集数据。此外，使用移动Sink可减少节点能耗[11]。

使用移动Sink可解决存在的一些实际问题，但使用移动Sink容易导致时延增加，特别是当数据量较大且节点高度分散的情况。当节点分布较广或数据量较大时如何降低时延是移动Sink数据收集的重要问题。为了尽可能降低时延，可采用多天线移动Sink进行数据收集。以往关于移动Sink的研究以单天线为主，近年来出现了对于WSN的多天线移动式数据收集的研究。多输入移动收集器在每一个锚节点位置作一定时间的停留进行数据收集[12-13]。多天线移动Sink在数据收集时需要考虑停留时间和最小能耗等问题[14]。通过建立多天线移动Sink数据收集的分布式框架，用SDMA技术来进行数据的多天线收集[15]。

WSN节点能量有限，需要尽可能减少能耗并且时延要低，因此如何设计具有较小能耗并且低时延的多天线移动Sink数据收集方法是一个难点。已有研究缺少从节点分布或网络结构方面进行讨论。本文在已有研究的基础上，通过对网络结构的分析构建高效的多天线移动Sink数据收集方法，提出基于度和集聚系数的多天线移动Sink数据收集（degree，clustering coefficient and common point for multi antenna mobile Sink data collection，简记 为DCCM）算法，该算法旨在降低节点能耗以及减小数据收集时延。

1 问题描述

假设监测区域中部署N个传感器节点，网络是不连通的，分割为若干个连通分支和多个孤立节点，通过多天线移动Sink进行数据收集。

若Sink的天线数目为a，在Sink的停留点存在c个数据流，2≤c≤a，同时上传数据到Sink，则称为并发上传数据。并发上传数据可以缩短数据上传的时间，但移动Sink的停留点的数据流需要和天线数目相匹配。然而如果片面追求数据流数目和天线数目相匹配，可能会导致移动Sink轨迹长度的增加，因此需要科学地选择移动Sink停留点。

数据收集时间包含Sink移动时间和数据上传时间，在缩短Sink移动时间的同时要使移动Sink停留点的数据流和天线数目相匹配，从而缩短数据上传时间。此外，Sink移动的轨迹长度和节点的能耗是相矛盾的，需要在缩短Sink移动的轨迹长度和节点的能耗之间取得平衡。

用图G来描述网络，设图G非连通，有连通分支G1，G2，…，Gm-1，Gm，各连通分支由已部署的节点组成，G1∪G2∪…∪Gm-1∪Gm。假设存在点集 S=可使G变为连通图，则称该点集中的点为虚拟点。

移动Sink的移动需保证每个节点都可被直接或间接通信到，移动Sink在停留点进行数据收集，数据收集过程中移动Sink有y个停留点，节点总能耗为E，数据收集的总时间（时延）为T，h表示跳数，则

多天线的应用可提高数据收集的效率，天线的空闲率要尽可能低，移动Sink的停留点需要具备与天线数目相匹配的度，或者在原本不相匹配的基础上改变数据流使其匹配，以进一步减小时延。问题的难点在于停留点的度和天线数目往往是不匹配的，若要达到高度的匹配有可能会增大Sink移动距离，因此需要从节点分布的角度加以分析。本文通过加入若干虚拟点，使可能不连通的节点分布成为一个连通图，从网络结构的角度对多天线移动Sink数据收集进行研究，达到降低网络能耗和时延。

2 多天线移动Sink数据收集

2.1 适应多天线移动Sink的分簇方式

各个连通分支和虚拟点一起构成连通图，然后从连通图的角度进行讨论。适宜多天线数据收集的条件：m（m≥2）个连通分支之间存在公共点，公共点之间距离要短。从图1可以看出高效的多天线移动Sink在节点随机部署情况下进行数据收集，从网络结构上来说需要具备大的集聚系数。因为需要移动Sink停留点具备与天线数目匹配的度（邻居节点数目），最理想的情况是Sink的每个停留点的度都是a。

定义1设点k的度为d，那么与点k最多有d(d-2)/2条连线，如果它的邻域中实际存在的连线数为E(k)，则点k的集聚系数为

图1 100个节点通信半径为40的随机部署统计

点的集聚系数用来描述图或网络中的顶点（节点）之间结集成团的程度，是一个点的邻接点之间相互连接的程度。集聚系数是一个介于0与1之间的数，集聚系数越接近1，表示这个节点附近的点越有集结成团的趋势。设d表示停留点的度，若d＞a，则需要将(d-a)个数据流并入a个数据流中，即移动Sink的停留点需要有大的集聚系数。由于dk=a，天线数目a是固定的，对于点的确定要看其邻域之间的连线是否紧密。首先计算网络中3个连通节点的总数，然后计算网络中三角形结构的总数，3倍三角形的总数在3个连通节点的总数中所占比例称为网络的集聚系数，即

其中N1表示网络中3个连通节点的总数，N2表示网络中三角形的总数。从能耗的角度分析，在数据并发上传到移动Sink过程中，当d＞a时，(d-a)个数据流需要并入a个数据流中，这时最节约能耗的情况是围绕着移动Sink所在位置有(d-a)个三角形结构。

在确定点的位置时，若数据流的数目与天线数目不相匹配时，通过寻找三角形的结构关系可以为移动Sink确定合适的停留位置。从全网的角度看，通过分析全网三角形结构的含量，可以判断多天线移动Sink是否得到充分使用。

2.2 多天线移动Sink数据收集的数据流分析

通过对WSN中数据流地分析，可以进一步为多天线移动Sink数据收集提供优化的依据。采用排队网络理论对WSN中数据流进行分析，排队网络指多个排队系统互相连接所组成的网络。

虚拟点和节点一起构成图，将虚拟点以及非叶节点（没有子节点的子节点叫做叶节点）称为中心。由于数据流是守恒的，存在以下3种情况：eia表示一个节点的数据到达中心i；eij表示一个节点在中心i处接收结束并转移到中心j；eid表示移动Sink在中心i处接收结束并离开。n表示各个队列中节点的数目。当存在平稳概率π(n)时，流出状态n的强度之和为

其中λ为数据流总流入强度，移动Sink到达中心点，然后转移到其他中心进行数据接收，因此

其中θi表示移动Sink在某中心接收结束后转移到中心i的概率，ni表示第i个服务中心的队长，πi(ni)表示中心i有ni个节点的概率。

其中π(n)表示停留点1的队长为n1，停留点2的队长为n2，依次类推，停留点M的队长为nM，δ为归一化因子，则

X（t）表示t时刻的状态，可以判断X（t）是一个马尔科夫过程。

通过以上的分析可知，若n＞nL，即队列长度大于队长限制nL，则希望π（n）小，π（n）表示各个中心平均队列长度为n的概率，π（n）小意味着M大。若n≤nL，即队列长度不大于队长限制，则希望π（n）大。停留点少或者负载均衡有利于π（n）大。由于停留点之间是相乘的关系，而队列长度的变化是相加的关系，停留点少的作用更显著，且增加停留点会加大时延，所以首先考虑减少停留点。当n≤nL时，队列长度n1≈n2≈…≈nM，即在负载均衡时，不通过减少停留点，也可使π（n）大。

减少停留点主要的因素是度和集聚系数。若需要停留点具备与天线数目匹配的度，全网的平均度要大于等于天线数目，这样才能充分发挥多天线对数据收集的作用。可能出现的情况有两种：一是停留点的度大于天线数目且集聚系数小，造成有的数据流无法并入其他数据流，即事件eij不能发生，从而移动Sink另外选择其他停留点；二是停留点的度小于等于天线数目，或者停留点的度大于天线数目且集聚系数大，停留点的度小于等于天线数目不能充分利用多天线的优势，使停留点的度大于天线数目且集聚系数大则可充分利用多天线的优势。

2.3 多天线移动Sink数据收集的路径规划

Sink移动的轨迹长度和节点的能耗是相矛盾的，需要在Sink移动的轨迹长度和节点的能耗之间取得平衡。若要降低节点能耗，会使移动Sink增大移动距离造成时延的增加。最极限的情况是移动Sink移动到每一个节点的一跳通信范围内，从而使节点的能耗最小。本文通过对虚拟点辅助形成的连通图分析，科学地选择移动Sink停留点，使数据收集过程中节点能耗与时延达到平衡。

停留点的度大于天线数目且集聚系数大则可充分利用并发上传的优势，但却有可能造成跳数过多的长链路。网络的平均距离的减小，不仅会使节点能耗降低，也会使Sink的移动距离减小。因此需要寻找有效减小网络平均距离的方法。

介数可以体现节点在网络中的重要性或影响力，大的介数对于跳数有减小的作用。介数通常分为点介数和边介数两种，本文所讨论的是点介数。

定义2设Ljk（i）表示节点j和节点k之间经过节点i的最短路径数目，Ljk表示节点j和节点k之间的最短路径数目，则点k的介数为

根据介数的定义可知，若G1和G2相同，由于本文中节点在某一时刻采用的是单一的转发方式，因此在本文中指相同的节点数，即当NG1=NG2时停留点k的介数最大。当NG1＞NG2或NG1＜NG2时，NG1∪NG2中经过停留点k的最短路径的次数不相等，停留点k的介数大于等于G1和G2中节点数多的一方的任一节点。因此若停留点k连通着独立连通分支G1和独立连通分支G2，则该点的介数不小于G1或G2中的任一节点。

Sink的停留点应选择位于介数之和最大的两个点c和d之间，c和d分别来自不同的连通分支，且两点距离Icd≤2R。

数据收集时间包含Sink移动时间和数据上传时间，在缩短Sink移动的轨迹长度的同时要使移动Sink的停留点的数据流和天线数目相匹配，从而缩短数据上传时间。对于停留点的选择需要其具备在大的集聚系数作用下与天线数目匹配的度以及可连接多个连通分支中介数大的点（或独立点）的公共点。通过前面的分析可知多天线移动Sink数据收集问题与网络结构密切相关，以下提出一种新的多天线移动Sink数据收集算法。

2.4 一种新的多天线移动Sink数据收集算法：DC⁃CM算法

DCCM算法主要过程：首先根据节点部署信息加入点（即虚拟点）构成连通图，然后从连通图的角度通过寻找优化的点的位置形成一系列停留点，从而确定Sink移动轨迹。

在监测区域中，设Sink起始点的坐标为（x0，y0）。根据前文的分析，本文提出的DCCM算法具体如下：

步骤1输入移动Sink起始点位置的坐标（x0，y0）。

步骤2找距（x0，y0）最近的连通分支（或独立的点）附近的点：

（Ⅰ）若dmax≤a，点唯一则作为停留点P1，点不唯一则转到第3步。

（Ⅱ）若dmax＞a，点唯一则作为停留点P1，通过数据流的整合使得d=a，若不能则寻找度第二大的点，再从第1步开始；若dmax＞a，有多个点均为dmax，则转到第3步，经过第3步若还无法确定停留点，则比较集聚系数，选择Cmax的点，通过数据流的整合使得d=a，若通过数据流的整合仍然d＞a，则在多个度均为dmax的点中寻找集聚系数第二大的点，进行数据流的整合。依次类推，如果根据集聚系数不能完成数据流整合，则寻找度第二大的点。

（Ⅲ）比较点是否为多个连通分支中介数大的点的公共点，若是则作为停留点P2。

步骤3若d＞a，则将d个数据流合并为a个数据流，Sink直线移至P1进行数据收集；若d≤a，则为d个数据流，Sink直线移至P1进行数据收集。

步骤4去除在P1位置Sink可通信的连通分支。

步骤5找距离P1最近的连通分支（或独立的点）附近的点，重复第2步选择点作为停留点P2。

步骤6 依次完成P1，P2，…，Pn。

步骤7判断移动Sink是否直接或间接通信过所有节点，若已完成，程序结束；若未完成，转至步骤5。

连接P1，P2，…，Pn位置即形成Sink轨迹。DCCM算法能够良好实现多天线移动Sink数据收集。DCCM算法的优点主要有：（1）可以较好地完成对并发上传数据和天线的匹配，其原因是当度与天线不匹配时可以通过大的集聚系数来调节，度和集聚系数的结合使多天线得到充分利用；（2）进一步降低了能耗以及缩短了Sink移动轨迹，其原因是多个连通分支中介数大的点的公共点作为Sink停留点，使平均跳数减少的同时缩短了Sink移动轨迹。

3 性能评估

为了验证算法的有效性，本文使用Matlab对DCCM算法进行仿真与分析。仿真实验部署的节点为全向节点，节点通信半径为R，在1 000×1 000的范围内，取R=40，a=2，随机部署节点，为便于对比，实验场景与文献[15]一致。

3.1 三角形结构含量的影响

通过统计随机部署的网络中的三角形结构含量，三角形结构含量大说明网络的集聚系数大，网络的集聚系数大可以为数据流提供更多的路径选择，为多天线完成其对并发上传数据的收集提供了便利，其中z表示三角形结构的含量。从图2可以看出三角形结构含量大有利于减小能耗，即集聚系数大有利于减小能耗，其原因是数据流有了更多的到达Sink的路径选择，便于数据流的优化重组。

3.2 网络能耗

图2 三角形结构含量对能耗的影响

假设收集相同的数据，均采用双天线。DaGCM算法[15]通过分裂数据来节约能耗，暂不收集远离停留点的数据，而在另外距此节点较近的停留点进行收集。而DCCM算法则通过寻找多个连通分支中介数大的点的公共点作为停留点进行数据收集。DaGCM算法加大了时延，而DCCM算法减小能耗的同时减小了时延。图3显示了在能耗方面的比较，可见DCCM算法优于DaGCM算法。因为运用点介数指标减小了平均跳数以及移动Sink轨迹长度，所以较好地减小了网络的能耗和时延。

图3 网络能耗对比

4 结论

移动Sink是面向复杂环境下WSN数据收集的一种有效方法。本文从网络结构的角度研究多天线移动Sink的数据收集问题。首先论证了多天线移动Sink数据收集问题包含的结构特征，然后提出了基于度、集聚系数以及多个连通分支中介数大的点的公共点的多天线移动Sink数据收集算法。仿真表明，该算法降低了网络的能耗以及时延。