无线传感网中基于信息增益最大化的泛在数据收集算法

宋三华

(黄淮学院 信息工程学院，河南驻马店 463000)

无线传感网中基于信息增益最大化的泛在数据收集算法

宋三华

(黄淮学院 信息工程学院，河南驻马店 463000)

基于移动设备的泛在数据收集是目前的研究热点。然而现有的数据收集方案关注的重点是提高数据收集的可靠性和能效，很少考虑传感器数据携带的信息价值。此外，移动用户可能没有足够多的时间收集周围传感器的所有数据。因此，有必要收集对于用户来说价值最大的数据。本文提出一种基于信息增益最大化的泛在数据收集算法。该算法首先利用移动设备可用容量估计值和传感器需求来自动确定数据收集树构建的最大层数，然后通过数据收集树的迁移来支持移动用户在自身移动性不受限制的条件下进行分布式数据收集。此外，移动用户可以根据自身速度，动态估计可以用于数据收集的设备容量。仿真实验结果表明，与当前最新的其他算法相比，本文算法可将信息价值提高50%、能耗降低50%。

移动设备；无线传感器网络；泛在数据收集；信息增益

0 引 言

随着移动设备的发展，泛在数据收集[1]使得用户利用他们的移动设备(比如PDA或者智能手机)从周围的传感器收集数据。这种架构增加了无线传感器网络(Wireless Sensor Networks, WSN)部署的灵活性，为传感器数据收集提供了一种高性价比解决方案[2,3]。与传统的WSN不同，泛在数据收集不需要依靠固定式Sink收集整个网络的传感器数据，而是利用移动设备从周围传感器中进行泛在收集数据。移动用户的移动性不受限制，无线通信范围有限，给泛在数据收集带来了挑战。具体来说，考虑到移动用户可能连续不断的快速移动，移动设备和传感器间的通信时间非常短。如何保证移动用户在有限的通信时间和无线容量下实现数据收集的信息增益最大化具有重要意义[4,5]。

Gu等人[6]提出一种基于分区的数据收集算法，通过对移动设备的运动进行调度，尽量降低了对移动速度的要求，避免了缓存溢出。Bisnik等人[7]研究了基于移动传感器的质量覆盖问题，分析了受控移动性对事件收集比例的影响。Xu等人[8]进一步研究了带有移动Sink的传感器网络延时容忍事件收集问题，考虑了事件在传感区域中的时空关联。He等人[9]从理论角度分析了数据收集的性能，利用一种排队模型评估了移动设备的服务准则。然而，上述研究均限制了数据收集时移动Sink的移动性，而本文中的移动用户为独立用户，其移动性不受限制。

另外还有，Kusy等人[10]提出一种算法利用训练数据来预测移动Sink的移动模式。他们计算并维护移动Sink的移动性图，以提升数据收集时的路由可靠性。类似地，Lee等人[11]提出一种路由算法，通过利用移动Sink的移动模式来尽量降低能耗和网络拥塞。Li等人[12]提出一种泛在数据收集算法λ-Flooding。该算法首先基于泛洪机制来构建数据收集树，然后在本地进行数据收集树的更新。然而总的来说，以上研究工作的重点是提高数据收集的可靠性和能效，他们没有考虑无线传感器网络数据收集时传感器数据携带的信息价值。此外，移动用户可能没有足够多的时间收集周围传感器的所有数据。因此，有必要收集对于用户来说价值最大的数据。本文提出一种分布式数据收集算法，通过对数据收集进行调度来实现数据收集信息增益的最大化。总的来说，本文主要贡献如下：首先，提出一种分布式数据收集算法EQRoute，实现移动用户基于信息价值的泛在数据收集。该算法支持移动用户在自身移动性不受限制的条件下进行分布式数据收集。其次，移动用户可以根据自身速度，动态估计可以用于数据收集的设备容量。最后，通过全面的仿真实验评估了EQRoute算法的性能。与当前最先进的其他算法相比，本文算法提高了数据收集时的信息价值，显著降低了能耗。

1 系统模型

1.1 应用场景

考虑图1所示的传感器监测区域，一个移动用户为了收集数据(比如温度，环境污染情况)而在传感区域中行走。监测区域中的传感器周期性地获得传感器测量值，并将其存储在缓存中。移动用户经过传感器时可以收集这些数据。本文利用信息价值来表示传感数据携带的各种观测值的重要性[13]。它经过正规化后范围在0到1之间，即w=[0,1]。一般而言，移动用户希望收集可使他们的信息价值最大的数据。例如。在图1中，如果用户用于数据收集的容量有限，则该移动用户将收集w=0.8而不是w=0.1的数据。图中的数字表示传感数据的信息价值。为了使信息增益最大化，信息价值大的数据在数据收集时具有较高的优先级。

图1 应用场景实例

1.2 挑战和设计目标

手机和无线传感器只有互相位于对方通信范围内时，二者才有机会通信。因此，如果移动用户在运动时移动性不受限制且难以预测，则收集无线传感器数据的难度很大。考虑到无线通信距离的有限性，比如IEEE 802.15.4或蓝牙标准明确的通信距离，当移动用户快速连续移动时，用于数据收集的通信时间很短。因为传感器和移动设备在相同的无线信道上通信，它们必须与周围的节点共享有限的无线容量。移动节点是接收并处理大量数据的数据收集树的根节点，所以移动节点很可能成为性能瓶颈。鉴于上述原因，移动用户有必要收集可使总体信息价值最大的数据，从而在保证数据收集质量的前提下，降低通信开销。为此，本文设计的泛在数据收集的目标是：(1)它支持基于信息价值的泛在数据收集，实现收集数据的信息价值最大化，且能耗较低。(2) 能根据移动用户的移动速度情况，提高数据收集的可靠性。(3)可采取分布式策略，对多个移动用户的数据收集进行协调。

2 基于信息价值的泛在数据收集

在数据收集过程中，传感器节点周期性地生成传感数据，并将数据缓存。支持兼容性无线组件的移动设备，比如IEEE 802.15.4或蓝牙设备，可从周围传感器中收集数据。以后连接互联网时，移动设备可将收集到的数据上载到服务器上。本文重点研究从无线传感器到移动用户的数据收集问题。我们的目标是实现信息价值的最大化，降低泛在数据收集的通信开销。移动用户模拟为一个移动性不受限制、通信范围有限、移动速度可变的移动单元(ME)。传感器只要位于移动单元的无线通信范围内，就可以与移动单元通信。将数据从无线传感器传输到移动用户时，可以采用多跳路由。

2.1 问题描述

(1)

(2)

(3)

(4)

其中，ui=wi/cij表示一个数据报文di每单位通信成本的信息增益，即收集数据的信息价值除以通信成本跳数。本文研究问题的目标函数是使所有收集数据的ui之和U最大化。约束2可保证每个报文di只被传输给一个移动用户。约束3允许一个报文中传输部分数据。约束4保证在一个给定时隙中，移动用户j接收到的所有报文不超过它的容量Cj。

2.2 集中式最优算法

算法1：集中式容量分配1：Cj：移动用户j的容量；2：wi：数据di的信息价值；3：cij：di到达j的跳数；4：5：移动用户j对网络中的所有传感器广播数据；6：每个传感器向j做出回应，回应数据的价值为wi，跳数为cij；7：whileCj>0do8： 选择可使wi/cij最大的di；9： ifCj>1then10： xij=1；11： else12： xij=Cj；13： endif14： Cj=Cj-xij；15：endwhile

定理1:上述贪婪算法可为传感器数据收集中的容量分配问题提供最优解。

证明：该算法为了接收传感器数据，将容量Cj全部分配完。假设容量有限，因此容量不足以收集网络中的所有数据。即存在一个q，使1=x1=…=xq-1>xq>xq+1=…=0，其中xn+1=0。通过与该问题其他解y1,…,yn做比较可证明算法1的解的最优性。因为对所有i，wi/cij均为正，如果∑iyi=Cj，则只有该解为最优解。用k表示可使yk<1的最小索引，用l表示可使yl>0且k0，将yk增加∈，yl减小，这样处理之后获得一个可行解，其价值不小于解y1,…,yn的价值。此外，要么yk等于1，或者yl等于0。重复上述推理，最终可以获得贪婪算法生成的解。证毕。

然而，该算法的工作模式为集中式模式。如上文所述，移动用户必须向整个网络注入数据，或者通过h跳传输进行广播，但是h难以确定。另外，上述集中式算法的能耗也较高。移动用户必须等待来自所有传感器的数据，然后才能向各个传感器分配容量，其通信开销的数量级是O(N)，其中N表示网络中的节点数量。

3 分布式算法设计

本节提出一种基于信息增益最大化的分布式泛在数据收集算法EQRoute。其主要思路是利用可用容量估计值Cj和传感器需求来自动确定数据收集树构建的最大层数。分布式设计也支持多个移动用户间进行数据收集协作。下面从两个方面给出本文分布式算法：数据收集树的构建，数据收集树的迁移。

3.1 数据收集树的构建

假设每个传感器生成高优先级数据和低优先级数据的概率分别为pH和pL，且pH+pL=1。它们的信息价值表示为wH和wL，且wH>wL。与大部分研究类似，在开始构建数据收集树时移动用户需要发送HELLO报文。然而，与算法1不同，我们没有向网络注入大量数据，或者广播预先确定的跳数，而是采取分布式策略，让每个节点检查其剩余容量，然后决定是否将树扩展到下一层。

(5)

其中，μj表示服务率，vj表示j的移动速度。移动用户j不断地根据其移动速度来估计自己的可用容量。本文通过运行CapacityAllocation(j,Cj)算法(算法2)来启动数据收集流程。

算法2：分布式容量分配1：dHi：节点i高优先级数据所需要的容量；2：dLi：节点i低优先级数据所需要的容量；3：fj：节点j的自由容量；开始时fj=Cj；4：5：ProcedureCapacityAllocation(j，fj)6：向所有单跳相邻节点广播HELLO信息；7：每个相邻节点i按照参数dHi和dLi做出回复； {//为数据H分配容量}8：for相邻节点i的每个回复do9： iffj+dLj>0then10： 为dHi分配容量；11： fj=fj-min(fj+dLj，dHi)；12： endif13：endfor {//为数据L分配容量}14：for每个dLido15：iffj>0then16： 为dLi分配容量；17： fj=fj-min(fj，dLi)；18： endif19：在endfor20：根据fi=fj/N(j)，为每个i分配剩余容量； {//扩展树}21：for每个相邻节点ido22： iffi>0then23： RunCapacityAllocate(i，fi)；24： endif25：endfor endProcedure

3.2 数据收集树的迁移

如上文所示，每经过时间Δt，移动用户便估计数据收集树的新容量。然而，由于移动用户移动速度和方向可能发生变化，移动用户和传感器间的通信仍然可能终止。因此，移动用户周期性地向相邻节点广播“MobileHere”维护报文，以通知相邻节点它仍然存在。总体来说，传感器被动等待维护报文。然而，如果没有接收到任何维护报文，则传感器也可以主动检测移动用户的存在情况。

此外，可以根据移动用户的新位置，利用MobileHere报文来更新树结构。例如，节点i如果直接接收到移动用户的维护报文，则可认为移动用户与它距离很近。节点i可以直接与移动用户通信，而不用通过中继节点采用更长的路径。利用树迁移策略便可处理这种情况。为了便于阐述，本文将迁移过程分为两种：内部树迁移和树恢复。 图2给出了内部树迁移的一个示例。开始时，移动用户只与数据收集树中的根节点A连接。然后，移动用户移动到可与其他传感器直接通信的新的位置。当节点B接收到移动用户的树维护报文时，它知道移动用户就在周围。然后，节点B成为其子树的根，直接与移动用户通信。更新完路由后，节点B通知其之前的中继节点A和移动用户相应地更新容量分配策略。

图2 内部树迁移示例

当根节点检测到与移动用户失去联系时，需要恢复数据收集树，树的恢复过程如图3所示。一旦根节点A检测到与移动用户失去联系，它便向相邻节点发送“FindMobile”树恢复报文，以便恢复连接。任何不属于A的子树的节点，可以帮助把报文中继传输给移动用户。在该例子中，节点B为节点A中继报文，于是A与移动用户恢复连接。与内部树迁移类似，树恢复后必须相应地更新容量。否则，移动用户可能认为A已经完成数据传输，但是A实际上仍在树中，且仍有很多数据待传。如果树恢复过程失效，节点A可以加入其他移动用户仍有空闲容量的数据收集树。为了避免出现路由环路，我们在树恢复报文中加入与移动用户直接连接的子树的根ID。只有具有不同子树ID的节点将对树恢复请求做出响应。

图3 数据收集树的恢复过程

4 仿真评估

本文利用OMNet++模拟器来评估本文算法EQRoute的性能。传感器和移动设备在非信标模式下基于IEEE 802.15.4进行通信。无线频段为2.4 GHz，数据率为250 kbit/s。在1000 m×1000 m区域上均匀部署100个传感器。无线传感器的通信范围R设置为100 m，且ΔD=100 m。移动用户的移动服从随机路点模型，且相互独立。在评估EQRoute时，设置pH=0.3，pL=0.7，且只考虑一个移动用户。传感器的数据生成率为8 B/s。在本文实验中，设置移动用户的移动速度为2 m/s～22 m/s，标准差为0.5 m/s。为了体现本文算法的优越性，将其与文献[12]提出的λ-Flooding算法在泛在数据收集方面的性能进行了比较。在λ-Flooding算法中，移动用户构建一个全局数据收集树，更新预先确定的阈值λ对树进行更新，以降低数据收集的能耗。

图4(a)给出了EQRoute和λ-Flooding接收到的报文总量。可以看出，二者报文数量相当。然而，本文EQRoute算法的能耗只有λ-Flooding的一半，如图4b所示。我们认为，λ-Flooding算法为了保持与移动用户的连接，需要延长路径，导致能耗提高。当速度增加时，λ-Flooding算法的平均跳数也会增加，这进一步证明了上述分析，如图4d所示。

图4 不同方案的仿真结果比较

图4c给出了收集到的数据消耗的单位成本(跳数)所对应的信息价值。EQRoute算法单位通信成本的信息价值，远高于λ-Flooding算法，这是因为本文算法在通信过程中为高价值数据赋予更高的优先权。我们还发现，在EQRoute算法中，移动用户速度增加时单位成本的信息价值也会增加。这是因为移动用户快速移动时构建的数据收集树，规模更小，跳数更少。

5 结 语

本文针对无线传感器网络中存在移动用户这一应用场景，提出一种基于信息价值最大化的泛在数据收集算法EQRoute。该算法为分布式算法，允许移动用户根据自己的移动速度来动态构建数据收集树。它还可以实现数据收集树规模的自适应控制，以降低能耗。通过为携带重要信息的数据分配高优先级，EQRoute提高了获取数据的信息价值。算法还支持多个移动用户间不用传输任何协调报文，便可就数据收集做出本地决策。仿真实验表明，本文算法和当前最新算法相比，信息价值提高了50%，能耗降低了50%。在下一步工作中，我们将在含有多个移动用户的传感器网络测试床上评估本文算法的性能。我们还打算通过预测移动特点来进一步提高分布式算法的性能。

[1] 陈燕, 张尚尚, 梁俊斌, 等. 无线传感网中生命最大化的泛在数据收集协议[J]. 计算机应用研究, 2014, 31(3): 866-871.

[2] 徐建波, 李仁发. 无线传感器网络中一种新型的混合型数据收集协议[J]. 计算机研究与发展, 2015, 45(2): 254-260.

[3] Ji S, Beyah R, Cai Z. Snapshot and continuous data collection in probabilistic wireless sensor networks [J]. IEEE Transactions on Mobile Computing, 2014, 13(3): 626-637.

[4] 胡升泽, 包卫东, 王博, 等. 无线传感器网络基于多元簇首的分簇数据收集算法[J]. 电子与信息学报, 2014, 36(2): 403-408.

[5] Hackmann G, Guo W, Yan G, et al. Cyber-physical codesign of distributed structural health monitoring with wireless sensor networks [J]. IEEE Transactions onParallel and Distributed Systems, 2014, 25(1): 63-72d

[6] Gu Y, Bozdag D, Ekici E, et al. Partitioning based mobile element scheduling in wireless sensor networks[C]// IEEE International Conference on Sensing, Communication, and Networks(SECON). New Orleans, USA:IEEE Press, 2013: 386-395.

[7] Bisnik N, Abouzeid A, Isler V. Stochastic event capture using mobile sensors subject to a quality metric[J]. IEEE Transactions on Robotics, 2014, 23(4): 676-692.

[8] Xu X, Luo J, Zhang Q. Delay tolerant event collection in sensor networks with mobile sink[C]// Proceedings of IEEE INFOCOM. San Diego, CA, USA: IEEE Press, 2010: 1-9.

[9] He L, Yang Z, Pan J, et al. Evaluating service disciplines for mobile elements in wireless ad hoc sensor networks[C]// Proceedings of IEEE INFOCOM. Orlando, FL, USA: IEEE Press, 2012: 576-584.

[10]Kusy B, Lee H J, Wicke M, et al. Predictive QoS routing to mobile sinks in wireless sensor networks[C]// Proceedings of the 8th ACM/IEEE International Confer-

ence on Information Processing in Sensor Networks(IPSN). San Francisco, CA, USA: ACM Press, 2009: 109-120.

[11]Lee H J, Wicke M, Kusy B, et al. Data stashing: energy-efficient information delivery to mobile sinks through trajectory prediction[C]//Proceedings of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks(IPSN). Stockholm, Sweden: ACM Press, 2010: 291-302.

[12]Li Z, Liu Y, Li M, et al. Exploiting ubiquitous data collection for mobile users in wireless sensor networks [J]. IEEE Transactions on Parallel and Distributed Systems, 2013, 24(2): 312-326.

[13]Kho J, Rogers A, Jennings N R. Decentralized control of adaptive sampling in wireless sensor networks [J]. ACM Transactions on Sensor Networks (TOSN), 2009, 5(3): 19-30.

关于《中国电子科学研究院学报》启用在线采编系统的通知

尊敬的作者：

您好,为了更好地服务于广大作者、审稿专家和读者,方便查询论文信息、投稿、询稿及审稿,提高杂志工作效率,《中国电子科学研究院学报》编辑部引进了期刊在线采编系统,目前已经正式开通，请您登陆如下网址，并注册进行投稿。在线采编系统启用后，我们将不再接收电子邮件投稿，造成不便，敬请谅解。

《中国电子科学研究院学报》在线采编系统网址：http://kjpl.cbpt.cnki.net。

在使用中如果有任何问题，请您及时与编辑部联系，联系电话：010-68893411

邮箱：dkyxuebao@vip.126.com

《中国电子科学研究院学报》编辑部

2016年4月20日

Ubiquitous Data Gathering Algorithm Based on Maximization of Information Gain in Wireless Sensor Networks

SONG San-hua

(College of Information Engineering, HuangHuai University, Henan Zhumadian 463000, China)

Ubiquitous data gathering based on mobile devices is a hot research topic at present. However, the existing data gathering schemes work has been focusing on the reliability and energy efficiency on data gathering. The information value carried by the sensing data has not yet been fully considered in data gathering for mobile sensor networks. In addition, the mobile users may not have enough contact time to collect all the data from the surrounding sensors. Hence, it is important to collect data that contain the most valuable information for the users. In this paper, a ubiquitous data gathering algorithm based on maximization of information gain is proposed. Which utilizes the estimated available capacity of mobile devices and the sensor demands to automatically determine the maximum layer for constructing the data collection tree, and then supports data collection for multiple mobile users with uncontrolled mobility in a distributed manner by migrating of data collection tree. In addition, the mobile users can estimate their available capacity for data collection dynamically according to their moving speeds. The simulation results show that the proposed algorithm can improve information value up to 50% and reduce energy consumption to 50% compared with the current latest approach.

Mobile devices; Wireless sensor networks; Ubiquitous data gathering; Information gain

10.3969/j.issn.1673-5692.2017.04.008

2017-05-01

2017-07-07

河南省科技厅发展计划项目(142102110088)

宋三华(1981—)，男，河南人，硕士，讲师，主要研究方向为网络及Android嵌入式系统应用;

E-mail： cjswzyhh@163.com

TP393

A

1673-5692(2017)04-371-07