2. 总参信息化部驻成都地区军事代表室, 成都 610041
部署在无线传感器网络监测区域的传感器节点周期性地进行感知数据的采集和传输, 传感器节点采集数据之间存在的空间关联性会增加采集数据的冗余度和网络能耗.为了延长无线传感器网络的生命周期, 提出了一种基于频繁项挖掘的空间关联性子簇形成算法.仿真实验结果表明, 该算法与已有算法相比, 降低了网络能耗, 延长了网络的生命周期, 保证了采集数据的质量.
2. Military Representative Office in Chengdu of Information Department of PLA General Staff, Sichuan Chengdu 610041, China
The cluster-based periodic data collection for wireless sensor networks, the sensor nodes deployed in monitoring region periodic transmit data to sink nodes were considered. The spatial correlation in collected data increases the redundancy of data and network energy consumption. An algorithm was proposed to prolong the lifetime of wireless sensor network and ensure the fidelity of collected data. A frequent itemset mining-based spatial subclustering algorithm was proposed. Analysis and experiment show that the improved algorithm can achieve more energy savings, extend the wireless sensor networks lifetime and guarantee the fidelity of collected data.
周期性数据采集是无线传感器网络的重要应用之一，传感器节点周期性地感知环境信息，并将感知数据传送到基站节点，传感器节点需要传输大量数据. Deborah Estrin指出传感器节点传输1 bit信息100 m距离需要的能量大约相当于执行3 000条计算指令消耗的能量[1].传感器节点的能量有限.因此，为了延长无线传感器网络的生命周期，研究如何减少节点间的通信量且保证采集数据质量的数据采集方法具有重要意义.
目前，减少基于分簇的周期性数据采集通信负载，降低数据采集的能量消耗已经取得了一些成果[2-8].
基于已有的研究成果，在分簇的传感器网络环境下，提出一种基于频繁项挖掘的空间关联性子簇形成算法(FIMSSC, frequent itemset mining-based spatial subclustering algorithm)，根据簇内节点采集的数据值，使用频繁项挖掘算法，获得簇内节点的空间关联性，根据关联性划分子簇.动态抽样选择子簇内节点感知上报数据，并可调整抽样率满足不同准确度的需求.这样，既能平衡节点能耗，又能降低网络中的数据通信量.
1 问题模型1.1 问题描述基于分簇的无线传感器网络数据采集，簇内节点周期性地传输感知数据到簇头节点，由簇头节点进行数据聚合并传送到基站节点.无线传感器网络结构用图G (S, H, B)表示，S代表传感器节点，H代表簇头节点，B代表基站节点.无线传感器网络由N个传感器节点组成，每个节点表示为si，i∈{1, 2, …, N}.分簇路由协议将无线传感器网络划分为互不相交的簇，网络中每一个节点都属于一个簇，每个簇都有一个簇头节点，被选为簇头的节点表示为hi，簇头节点集合H表示，H={si|hi=si}. hi=si表示节点si是簇头节点.
1.2 模型建立基于存在的问题提出空间关联性子簇网络结构，将簇进一步划分为子簇，Ci中的子簇集表示为Gi. Ci中子簇的数量由Ki表示，Ki＝|Gi|，无线传感器网络关联性子簇模型如图 1所示.
|
图 1 空间关联性子簇模型 |
FIMSSC算法的核心思想是根据节点感知的数据使用频繁项挖掘算法获取节点的关联性.算法由3部分组成，基站节点挖掘簇内节点的关联性；簇头节点根据节点的关联性进行传感器调度；随着环境变化动态调整簇内节点的关联性.
2.1 挖掘簇内节点关联性根据基站节点的性能，设定挖掘的时间范围n，选取簇内所有节点在此区间内采集到的数据序列.设置可容忍的误差值σ，2个数据的差值小于σ，认为这2个数据相等，定义传感器节点的字典序[9]. S1S2S3…SN.挖掘簇内节点关联性分3个阶段.
阶段1 形成记录.根据簇内每个节点的时间序列，将相同采样周期感知到相同数据(数据差值在可容忍误差范围内)的传感器节点按字典序形成一条记录.
阶段2 构建树形结构.根据n个采样周期形成的记录构建树形结构[10]，并建立global header table，根据记录构建的树如图 2所示.
|
图 2 树形结构 |
阶段3 树的挖掘.设定最小支持度support，对构建的树挖掘，挖掘方法与FP-growth Algorithm[11]相似.最终得到的项集感知到相同数据的次数大于等于最小支持度计数.最小支持度计数＝support×n.过程如下所示.
1) 从global header table最后一项开始，构造包含此项的条件数据库，每条记录不包含已经挖掘出的项集所包含的项.
2) 为此条件数据库构建相应的条件FP-tree[11]，将单项计数小于最小支持度计数的项删除.
3) 深度优先浏览条件FP-tree的每一个分枝，挖掘满足最小支持度计数的最长频繁项集.
4) 从获得的节点序列中选择最长的序列，此过程得到频繁项集.将global header table中的此频繁项集包含的项删除.
5) 循环执行以上过程，直到global header table为空结束.
最终，簇内所有的传感器节点划分为互不相交的子集.
2.2 基于空间关联性的传感器调度基站节点根据簇内节点采集的数据挖掘节点之间的关联性，按关联性将簇划分为多个子簇，在子簇内选择抽样节点感知并上报数据，簇内至少有一个子簇选择多于一个抽样节点，抽样节点动态随机选取，且抽样节点更新周期TS，子簇内选择多个节点上报数据.基站节点将子簇的划分结果散布给簇头节点，簇头选择子簇的抽样节点，使簇内至少有一个子簇多于一个抽样节点，并通知被选为抽样节点的簇内节点感知并上报数据，簇头节点对同一子簇内节点的时间序列进行比较，当n个连续数据，存在大于n (1-support)个数据的差值大于可容忍误差σ，则认为簇内节点的空间关联性发生改变.
2.3 动态调整当簇头节点探测到簇内节点的空间关联性发生改变，则通知簇内所有节点按照采集周期感知并上报数据，由基站节点进行簇内节点空间关联性的挖掘，重新划分子簇.设定重新形成簇的时间周期Tc，当采集数据区域的空间关联性保持稳定，不频繁地发生改变，则子簇不会频繁地进行更新，因此，会减少数据通信量，降低网络能耗.通过挖掘节点的空间关联性，延长网络生命周期，适用于空间关联性比较稳定的环境.
3 实验为测试提出的数据采集优化算法，从网络能耗和数据恢复准确性两方面进行仿真.
3.1 网络能耗仿真为了测试优化方法在基于分簇的无线传感器网络中进行数据采集时对网络能耗和生命周期的影响，选用网络仿真工具NS2作为仿真平台.实验在LEACH协议的基础上加入优化策略.模拟实验环境，在100 m×100 m的平面区域随机部署100个传感器节点，基站坐标为(50, 75).实验中，设每个节点的初始能量为2 J，{S1S2S3…SN}，εm=0.001 3 PJ/(bit·m4), Eelec=50 nJ/bit，Eda=5 nJ/(bit·sin gal－1)，带宽为1 Mbit/s，消息长度500 Bytes，发送和接收时延25 μs，簇的更新时间间隔20 s，仿真时间为600 s.优化方法与LEACH协议相比，网络的能量消耗如图 3所示，优化方案在500 s内没有出现死亡节点，并且能耗为160 J，相比较LEACH协议，降低了网络能耗.每一轮中，簇的形成和稳定所占的时间比例不变，改变抽样率，选择14%、28%、42%、56%节点作为抽样节点，如图 5所示网络能耗与抽样率成正比.
|
图 3 节点总能耗随时间变化情况 |
|
图 5 恢复数值与实际数值比较 |
选择公开的数据集Intel Berkeley Lab Data.实验选择2月28日的温度数据进行数据准确性的分析.设最大可容忍误差为1，选择13:30—14:00时间段的数据，挖掘节点之间的关联性.以其中一个具有空间关联性的集合为例，抽样值与实际采集的数值比较如图 5所示，采样时间点在14:00—14:30，节点之间的空间关联性没有改变，并且两者之间的误差值在设置的最大可容忍误差范围内，保证了采集数据的准确性. 图 6比较了不同抽样率对数据准确性的影响，分别选择2个节点、3个节点、4个节点作为抽样节点，计算均值作为未选作抽样节点的数值，与实际采集的数值进行比较.首先，恢复的数据值与实际采集的数据值之差在最大可容忍误差范围内；第二，抽样节点越多，抽样率越大，恢复数据的准确度越高，但是差别不大，越多抽样节点上报数据，能量的消耗越大，如图 4所示，所以并不是越多节点上报数据越好，最好选择2个节点作为抽样节点.
|
图 4 不同抽样率下节点总能耗情况 |
|
图 6 不同抽样率对恢复数据准确率比较 |
提出一种基于频繁项挖掘的空间关联性子簇形成算法，优化分簇的数据采集方法.在随机部署的无线传感器网络仿真环境中，证明提出的数据采集优化算法在减少网络能耗，延长网络生命周期方面有良好的表现.
| [1] | Estrin D. Wireless sensor networks tutorial part Ⅳ: sensor network protocols[C]//Proceedings of the Invited Speech of International Conference on Mobile Computing and Networking(Mobicom). Atlanta, USA: [s. n. ], 2005. |
| [2] | Abbasi, Ameer Ahmed, Mohamed Younis. A survey on clustering algorithms for wireless sensor networks[J].Computer Communications, 2007, 30(14): 2826–2841. |
| [3] | Bagci H, Yazici A. An energy aware fuzzy approach to unequal clustering in wireless sensor networks[J].Applied Soft Computing, 2013, 13(4): 1741–1749. doi: 10.1016/j.asoc.2012.12.029 |
| [4] | Nikolidakis, Stefanos A. Energy efficient routing in wireless sensor networks through balanced clustering[J].Algorithms, 2013, 6(1): 29–42. doi: 10.3390/a6010029 |
| [5] | Jiang Hongbo, Jin Shudong, Wang Chonggang. Prediction or not? An energy-efficient framework for clustering-based data collection in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems, 2011, 22(6): 1064–1071. doi: 10.1109/TPDS.2010.174 |
| [6] |
宋欣, 王翠荣. 基于线性回归的无线传感器网络分布式数据采集优化策略[J]. 计算机学报, 2012, 35(3): 568–580.
Song Xin, Wang Cuirong. Linear regression based distributed data gathering optimization strategy for wireless sensor network[J].Chinese Journal of Computers, 2012, 35(3): 568–580. |
| [7] |
杨军, 张德运, 张云翼, 等. 基于分簇的无线传感器网络数据汇聚传送协议[J]. 软件学报, 2010, 21(5): 1127–1137.
Yang Jun, Zhang Deyun, Zhang Yunyi, et al. Cluster-based data aggregation and transmission protocol for wireless sensor networks[J].Journal of Software, 2010, 21(5): 1127–1137. |
| [8] | Jiang Hongbo, Jin Shudong. Leap: localized energy-aware prediction for data collection in wireless sensor networks[C]//Mobile Ad Hoc and Sensor Systems, MASS 2008, 5th IEEE International Conference on. [S. l. ]: IEEE, 2008: 491-496. |
| [9] | Leung CK-S, Quamrul I Khan, Tariqul Hoque. CanTree: a tree structure for efficient incremental mining of frequent patterns[C]//Fifth IEEE International Conference on Data Mining. [S. l. ]: IEEE, 2005. |
| [10] | Tanbeer, Syed Khairuzzaman. Efficient mining of association rules from wireless sensor networks[C]// Advanced Communication Technology, ICACT 2009, 11th International Conference on. [S. l. ]: IEEE, 2009. |
| [11] | Han Jiawei, Jian Pei, Yin Yiwen. Mining frequent patterns without candidate generation[C]//ACM SIG MOD International Conference on Management of Data. New York, USA: ACM, 2000, 29(2): 1-12. |