最小开销启发式算法在物联网数据采集的研究*

康志辉

(厦门软件职业技术学院)

0 引言

物联网(Internet of things，IOT)是目前新兴的研究热点，已作为一种重要技术出现在许多领域中，如交通、医院、天气检测、大型商场等.同时，随着无线传感网络的改进，使得无线移动设备如智能手机、平板电脑的销量得到迅速增长，智能手机、平板电脑的数据交换和移动性支持已能够满足WSN在这些领域下的集成和拓展.物联网中的数据采集是通过无线传感网络(Wireless Sensor Networks，WSN)进行的.传感器、执行器、控制器和通信装置共同构成了无线传感网络，该网络集传感与驱动控制能力、计算能力、通信能力于一身，实现对物联网中数据资源的获取、计算和存储［1］.由这些微型传感器构成的无线传感器网络能够实时监测、感知和采集物联网中分布在各个区域中的监测对象信息，实现对这些信息的加工与处理，并将其传送给需要这些信息的用户.

对于物联网中数据的采集，文献［2］用多接收器在WSN中对数据采集进行了研究.它们定义了一种近似模型尝试最小化数据采集延迟，同时保证拥有常数因子的性能.文献［3］将WSN中的数据采集阶段归为3类:部署阶段、控制消息传播阶段和数据传输阶段.每个阶段都有它自己的特征和挑战.文献［4］研究WSN数据采集中由不同种类采集场景引起的容量挑战，其提出了一种可以控制该问题的渐近上界方法.文献［5］提出的方法采用网络建模，预测网络内的能耗并尝试优化它.文献［6－7］中尝试解决数据采集的挑战.在极大程度上，该工作已经聚焦于传感器间的最大化数据采集量、最小化数据延迟或最小化能耗.但是，目前还没有研究尝试结合这些目标来平衡这些冲突目标的结果.

1 物联网数据采集设备及过程

物联网中数据采集过程中WSN的生存期与它的传感器的生存期成正比关系.如果一个传感器在电量耗尽时是一个关键节点，即处于任何到达目的节点(数据接收器)的路由中心，它的损失会导致整个网络的损失.因此，对于任何动态WSN，在保存或平衡传感器的能量消耗时，以一种可靠的方式来收集数据是很重要的.传感器节点一般由传感单元、数据处理单元、数据收发单元、电源单元等功能模块组成，如图1所示.

图1 WSN节点构成

通常，WSN由大量电池驱动的传感器组成，它们以随机或受控制的方式在区域进行部署［8］.每个传感器只需要寻找位于它通信范围内的相邻节点.所提数据接收器将会是一个接收感应数据的移动手持设备.该设备可以是一个便携式设备(如手机、平板电脑等)，可携带用来在感应区周围采集数据.该设备可称为传感器数据管理器(Sensor Data Manager，SDM).传感器数据管理器具有需要的软件和接口，以使得它表现为一个网络调节器、数据接收管理器和传感器分配协调器.该架构的思想是它以最小的设备需求在需求环境下设置.这样的动态/移动数据接收器的出现，将会消除在不受控部署域下建立或完成特定传感器的必要.WSN下的节点从它周围节点感应数据，将数据传输到能量更强的称为数据接收器的节点，并聚合和分析感应接收到的数据.图2展示了物联网中的一种部署示例，SDM订阅了WSN以及来自网络的传感器S1提供数据的请求.

图2 WSN布局

2 最小开销启发式算法

启发式算法(Heuristic Algorithm)是相对于最优化算法提出的.启发式算法定义如下:一个基于直观或经验构造的算法，在可接受的花费(指计算时间和空间)下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计［9］.

该文设计了支持物联网数据采集通信协议的最小开销启发式算法进行相关数据的采集.在该通信协议中，初始化阶段是通过移动Sink经过执行三轮移动完成的.尽管绝大部分的耗时耗能任务都是由移动Sink完成的，但过长的初始化操作依然会给物联网的数据采集带来低效率.为此，本节给出一种最小开销启发式算法，通过该算法实现物联网中各个成员节点通过分布式的方式独立进行目的Sub－sink的选择，通过目的Sub－sink的选择实现物联网中各个成员和Sub－shik之间的优化匹配，进而降低整个网络的能量消耗.最小开销启发式算法的具体过程如下:

Step1:在移动Sink的第一轮移动过程中，首先选中靠近轨道的传感器节点.

Step2:整个物联网范围内最短路径树的建立由Sub－sink发起;

Step3:各Sub－sink之间通信的起止时间通过移动Sink进行记录.该起止时间用于计算物联网中各Subsink点之间的有效的通信时间以及各个成员对数据量的需求;

Step4:在移动Sink的第二轮移动过程中，移动Sink将各个成员对数据量需求的计算结果进行物联网中相应监测区域的扩散;

Step5:物联网中每个成员节点通过计算获得到达所有Sub－sink点的最短跳数;

Step6:根据最短跳数获得各个Sub－sink点的成员数量需求;

Step7:各个成员节点通过运行最小开销分布式算法进行合适的Sub－sink的选择;

Step8:通过确定的Sub－sink实现物联网中数据的采集与传输;

Step9:数据采集是否结束，若是，转Step 10，否则，转Step 3;

Step10:算法结束.

在最小开销分布式算法中，通过引入权重值α来计算各个Sub－sink的优先级，该优先级体现了各个Sub－sink被选作为最终目的地的概率大小.若α值较小，则说明跳数信息比成员数量需求信息的优先级高.具体的最小开销分布式算法见表1.

该文的最小开销启发式算法仅需要两轮Sink移动周期即可完成数据采集的初始化操作，而且与集中式算法相比，其协议效率更好.除此之外，该文最小开销启发式算法中目的Subsink的选择算法较遗传算法更为简单.通过该文算法，为了适应物联网数据采集节点的失效或新增的数据采集节点带来的无线网络拓扑结构的改变，可以通过让部分成员节点独立运行，该文的最小开销启发式算法方式来获取临时可用的Sub－sink.

表1 最小开销分布式算法(对任意成员)

3 仿真研究

该文的仿真平台是通过SimJava开发的，相应的仿真实验是通过该平台完成的［10］.通过该仿真平台进行了该文提出的最小开销数据采集方法与两种基准方法:随机法和贪心能量感知法进行了对比与评估，证明了该文方法的有效性.

随机法是一种遍历和聚合来自物联网中WSN数据的简单随机数据采集协议，该种方式是一种简单的基准方法，它无需任何的数据交换或者信息共享.该文的最小开销启发式算法与随机法相比，更有助于计算所提方法的额外开销.第二种比较的数据采集方法是贪心能量感知算法，该算法尝试使用最短路径算法来收集物联网中的感应数据.在该方法中，该协议将会确保遍历路径中拥有最高电池电量的节点，以选择到达SDM的最短路径.该方法也被称之为贪心能量感知(Greedy Power Aware，GPA)数据采集器.该贪心算法将会提供整个物联网中WSN可能能耗的最大值，因为它通常尝试选择拥有最大功率级的路径.

图3展示了针对数据采集成功率三种方法的仿真结果.通过图3可以看出，在三种方法中贪心能量感知方法表现最好，作为一种纯粹的数据采集方法，贪心能量感知法通过能找到最短路径(最小延迟).该文所提出的最小开销启发式算法比贪心能量感知法稍差(特别当低通信量和极端通信量时)但是优于随机方法.

图3 三种方法针对物联网数据采集成功率的仿真对比

图4显示了针对网络中每个传感器节点的平均能耗以及能量消耗速率三种方法的仿真实验结果.通过图4可以看出，贪心能量感知模型优于尝试选择拥有最高能量级的最短路径来最大化物联网中传感器电池在数据采集中的使用期限，因此，其能力消耗速率是比较高的，但是优于随机的方法.该文所提的基于最小开销启发式算法在三种方法中是表现最好的.该文方法是通过一种受控启发式算法进行执行的，因此在WSN上不会产生额外开销.另外需要注意的是，贪心能量感知法在任何时间节点都需要WSN的一个全局视图.这表示拓展性和执行开销将会是该方法的一个主要问题.

图4 三种方法针对能量消耗速率的仿真对比

图5显示了三种方法针对物联网中数据采集时的通信负载的仿真实验对比.该仿真对每次数据采集所需要的通信和执行开销进行对比.该测量值包括了物联网数据采集传感器节点间为了更新WSN关于每个节点的统计信息的数据交换，以及在每个节点间执行路由选择算法的开销总和.与贪心能量感知方法相比，该文所提出的最小开销启发式算法在数据采集时的通信开销随着数据采集频率的增长是有弹性的.而，贪心能量感知的通信开销随着通信量增长而呈指数增长，因此其能量消耗是巨大的.随机法的能量消耗介于两种方法之间.该仿真显示了所提启发式算法的真实优点.

图5 三种方法针对数据采集节点的通信开销的仿真对比

4 结束语

基于物联网的数据采集使得设备的位置通过网络以一种动态的方式进行数据分享.物联网中无线网络的不稳定无线连接和有限的能量资源，带来了数据采集的新的挑战.物联网中的数据采集是挑战的核心，需要将采集到的各种数据信息进行聚集、融合并经过路由器传送到最终的目的节点.数据感应和数据路由的活动会对传感器的电池能量造成损失，这将导致WSN的重新组合.该文所提出的最小开销启发式算法是一种适应性数据采集方法，仅需要两轮Sink移动周期即可完成数据采集的初始化操作，而且与集中式算法相比，其协议效率更好.该方法相对于传统的随机法和贪心能量感知法具有更低的开销.下一步将围着这网络传感网中的感应、处理、通信和行动的合作和协同展开研究.

［1］蒋凌云，孙力娟，王汝传，等.移动无线传感网能量时延约束的自适应路由及性能评估［J］.电子学报，2013，40(12):2495－2500.

［2］Chen Sixia，et al.Data collection with multiple sinks in wireless sensor networks［J］.Wireless Algorithms，Systems，and Applications.Springer Berlin Heidelberg，2009，5682(13):284－294.

［3］Mainetti L，Patrono，Vilei A.Evolution of wireless sensor networks towards the internet of things:A survey［J］.Software，Telecommunications and Computer Networks，2011，19(15):1－6.

［4］Fan Xiuwei，Lei Jianshu.一种轻量级的 WSN认证和密钥协商方案［J］.计算机工程，2013，39(3):146－151.

［5］Del Cid P J，Matthys N，Hughes D，et al.Resource management middleware to support self managing wireless sensor networks［J］.2010 Fourth IEEE International Conference on，2010，10(4):251–255.

［6］Awan A，Jagannathan S，Grama A Y.Scalable Data Collection in Dense Wireless Sensor Networks［J］.2007，7(18):1－9.

［7］Liang Zhang，Ye Qiang，Cheng Jie，et al.Fault－ tolerant scheduling for data collection in wireless sensor networks［J］.In GlobalCommunicationsConference(GLOBECOM)，2012，10(3):5345–5349.

［8］王翥，吕翠翠，陈建辉.基于贪婪算法无线传感器网络中继节点布局的研究［J］.计算机应用研究，2014，31(2):485－487.

［9］王景存，张晓彤，陈彬，等.一种基于 Dijkstra算法的启发式最优路径搜索算法［J］.北京科技大学学报，2007，29(3):346－350.

［10］Kreutzer W，Hopkins J，Van Mierlo M.SimJAVA－a framework for modeling queueing networks in Java［C］//Proceedings of the 29th conference on Winter simulation.IEEE Computer Society，1997.483–488.