无线传感器网络中基于熵评判的关联支配集构造算法

第３４卷第１期　计　算　机　学　报　Ｖｏ１．３４　Ｎｏ．１　２０１１年１月　ＯＦ　Ｃ０ＭＰＵＴＥＲＳ　ＣＨＩＮＥＳＥ　ＪＯＵＲＮＡＬ　Ｊａｎ．２０１１　无线传感器网络中基于熵评判的关联支配集构造算法　于瑞云”　王兴伟　”（东北大学软件学院沈阳　（东北大学信息科学与工程学院　沈阳　ｌ１０８１９）　”（德克萨斯大学阿灵顿分校计算机科学与工程系　美国德克萨斯７６０１９）　摘　要无线传感器网络通常是密集分布的，因此相邻网络节点感知的数据之间具有很大的相关性．为了在无线　传感器网络中进行数据冗余缩减，文中提出了一个基于熵评判的关联支配集构造算法（ＥＥＣＤＳ），算法首先通过评　价高斯随机变量的熵值来判断网络节点间的数据相关性，然后分布式地构造一个关联图，最后根据关联图信息移　除网络中的冗余节点，构建一个连通关联支配集．基于连通关联支配集的数据采集策略能在密集无线传感器网络　中进行高效的数据冗余缩减，显著降低网络的能量消耗，延长网络的生命周期．　关键词无线传感器网络；信息熵；微分熵；关联图；关联支配集；冗余缩减　ＴＰ３９３　ＤＯＩ号：１０．３７２４／ＳＰ．Ｊ．１０１６．２０１ｌ＿０００８７　中图法分类号刘　永㈣　Ｃｏｒｒｅｌａｔｉｏｎ　Ｄｏｍｉｎａｔｉｎｇ　Ｓｅｔ　Ｃｏｎｓｔｒｕｃｔｉｏｎ　Ｂａｓｅｄ　ｕｐｏｎ　Ｅｎｔｒｏｐｙ　Ｅｖａｌｕａｔｉｏｎ　ｉｎ　和　Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ　ＹＵ　Ｒｕｉ—Ｙｕｎ”　ＷＡＮＧ　Ｘｉｎｇ—Ｗｅｉ。　ＬＩＵ　Ｙｏｎｇ—Ｈｅ”　（Ｓｏｆｔｗａｒｅ　Ｃｏｌｌｅｇｅ．Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ．Ｓｈｅｎｙａｎｇ　１１０８１９）　（Ｃｏｌｌｅｇｅ　ｏＪ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｎｏｒｔｈｅａｓｔｅｒｎ　Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈｅｎｙａｎｇ　１１０８１９）　。　（Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｅｎｇｉｎｅｅｒｉｎｇ　Ｄｅｐａｒｔｍｅｎｔ．ｔｈｅ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｔｅｘａｓ　ａｔ　Ａｒｌｉｎｇｔｏｎ，ＴＸ　７６０ｌ９，ＵＳＡ）　Ａｂｓｔｒａｃｔ　Ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ　ａｒｅ　ｕｓｕａｌｌｙ　ｄｅｎｓｅｌｙ　ｄｅｐｌｏｙｅｄ，ＳＯ　ｔｈｅ　ｄａｔａ　ｓｅｎｓｅｄ　ｆｒｏｍ　ｎｅｉｇｈ—　ｂｏｒｉｎｇ　ｓｅｎｓｏｒ　ｎｏｄｅｓ　ｉｓ　ｈｉｇｈｌｙ　ｃｏｒｒｅｌａｔｅｄ．Ｆｏｒ　ｒｅｄｕｎｄａｎｃｙ　ｒｅｍｏｖａｌ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ，　ｔｈｉｓ　ｐａｐｅｒ　ｐｒｅｓｅｎｔｓ　ａｎ　ａｌｇｏｒｉｔｈｍ　ｎａｍｅｄ　ｅｎｔｒｏｐｙ　ｅｖａｌｕａｔｉｏｎ　ｆｏｒ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｃｏｎ—　ｓｔｒｕｃｔｉｏｎ（ＥＥＣＤＳ）．Ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｆｉｒｓｔ　ｄｅｔｅｒｍｉｎｅｓ　ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｅｇｒｅｅ　ｂｅｔｗｅｅｎ　ｓｅｎｓｏｒ　ｎｏｄｅｓ　ｂｙ　ｅｖａｌｕａｔｉｎｇ　ｔｈｅ　ｅｎｔｒｏｐｙ　ｏｆ　Ｇａｕｓｓｉａｎ　ｒａｎｄｏｍ　ｖａｒｉａｂｌｅｓ，ａｎｄ　ｔｈｅｎ　ｄｉｓｔｒｉｂｕｔｉｖｅｌｙ　ｇｅｎｅｒａｔｅｓ　ａ　ｃｏｒｒｅ—　ｌａｔｉｏｎ　ｇｒａｐｈ．Ｂａｓｅｄ　ｏｎ　ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｇｒａｐｈ，ｔｈｅ　ＥＥＣＤＳ　ａｌｇｏｒｉｔｈｍ　ｆｉｎａｌｌｙ　ｃｏｎｓｔｒｕｃｔｓ　ａ　ｃｏｎｎｅｃｔｅｄ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｂｙ　ｒｅｍｏｖｉｎｇ　ｒｅｄｕｎｄａｎｔ　ｓｅｎｓｏｒ　ｎｏｄｅｓ．Ｄａｔａ　ｇａｔｈｅｒｉｎｇ　ｐｏｌｉｃｉｅｓ　ｗｉｔｈ　ｔｈｅ　ｈｅｌｐ　ｏｆ　ｃｏｎｎｅｃｔｅｄ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔｓ　ｗｉｌｌ　ｇｒｅａｔｌｙ　ｒｅｄｕｃｅ　ｄａｔａ　ｒｅｄｕｎｄａｎｃｙ　ｏｆ　ｄｅｎｓｅ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ，ａｎｄ　ｔｈｅｒｅｆｏｒｅ　ｒｅｓｕｌｔ　ｉｎ　ｄｅｃｒｅａｓｅ　ｏｆ　ｅｎｅｒｇｙ　ｃｏｎｓｕｍｐｔｉｏｎ　ａｎｄ　ｐｒｏｌｏｎｇ　ｌｉｆｅｔｉｍｅ　ｏｆ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋＳ　Ｋｅｙｗｏｒｄｓ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ；ｉｎｆｏｒｍａｔｉｏｎ　ｅｎｔｒｏｐｙ；ｄｉｆｆｅｒｅｎｔｉａｌ　ｅｎｔｒｏｐｙ；ｃｏｒｒｅｌａｔｉｏｎ　ｇｒａｐｈ｝ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ；ｒｅｄｕｎｄａｎｃｙ　ｒｅｍｏｖａｌ　收稿日期：２００８～¨一２０；最终修改稿收到日期：２０１０－１２—２０．本课题得到国家自然科学基金（６１０７０１６２，７１０７１０２８，６０８０２０２３，７０９３１００１）、高　等学校博士学科点专项科研基金（２０１０００４２１１００２５，２００７０１４５０１７）、高校基本科研业务费专项资金（Ｎ０９０５０４００３，Ｎ０９０５０４００６，　Ｎ１００４１７００１）和辽宁省博士科研启动基金项目（２０１０１０４０）资助．于瑞云，男，１９７４年生，博士，讲师，主要研究方向为无线自组通信、无线　传感器网络、多传感器数据融合等．Ｅ　ｍａｉｌ：ｙｕｒｙ＠ｍａｉｌ．ｎｅｕ．ｅｄｕ．ｅｌ１．王兴伟，男，１９６８年生，博士，教授，博士生导师，主要研究领域为下　一代互联网、移动Ｉｎｔｅｒｎｅｔ和ＩＰ／ＤＷＤＭ光Ｉｎｔｅｒｎｅｔ等．刘永和，男，１９７４年生，博士，副教授，主要研究方向为无线组网、传感器网络、安　全、系统集成等．　８８　计　算　机　学　报　均衡特性和可扩展性．　１　引　言　２　网络模型　无线传感器网络是由大量具有感知、数据处理　和通信能力的传感器节点组成的网络，并且通过传　感器节点之间的协作，实现对各种现象的监测．由于　具有低功耗、低成本、智能化、分布式、自组织等特　将无线传感器网络模型化为一个单位圆图　Ｇ（Ｖ，Ｅ），其中　表示网络节点集，Ｅ为在通信半径　范围内的节点所形成的边的集合．假定网络是密集　点，无线传感器网络在军事、环保、医疗、商业、灾害　预测及救援等领域有着广阔的应用前景．　无线传感器网络通常是密集分布的，因此网络　节点感知的数据之间通常具有很大的冗余性．由于　传感器网络节点是能量受限的，支持冗余缩减的技　术能在很大程度上减少网络的能量消耗，从而能够　延长无线传感器网络的生命周期．　很多文献提出通过冗余缩减的方法减少在网络　中传输的数据量，进行高效数据获取．　文献［１—５］采用编码策略来消除网络中冗余数　据，减少向汇聚节点传输的数据量；文献［６—７］提出　随机树构造算法为单汇聚节点的数据采集应用构造　数据融合树，网络节点感知的数据在向汇聚节点传　送的过程中可以在中间网络节点上进行数据融合；　文献［８—９］提出的方法都是结合无线传感器网络节　点的空间相关度，研究从网络中选取一部分节点向　汇聚节点传输感知的数据，以此消除无线传感器网　络中的冗余数据．　本文在关联图和关联支配集概念的基础上设计　了一个基于熵评判的关联支配集构造算法（Ｅｎｔｒｏｐｙ　Ｅｖａｌｕｔｉｏｎ　ｆｏｒ　Ｃｏｒｒｅｌａｔｉｏｎ　Ｄｏｍｉｎａｔｉｎｇ　Ｓｅｔ　Ｃｏｎ—　ｓｔｒｕｃｔｉｏｎ，ＥＥＣＤＳ），构造一个连通关联支配集对剩　余节点进行关联支配，并利用连通关联支配集中的　节点进行数据感知、采集和传输，实现数据冗余缩减　的目的．　文献［８—９］提出的方法与本文类似，但文献［８］　只考虑直接邻居节点之间的相关性．与本文提出的　算法一样，文献［９］也考虑了ｋ跳邻近节点的相关　性，本文提出了一个熵评判（ｅｎｔｒｏｐｙ　ｅｖａｌｕａｔｉｏｎ）方　法，与文献［９］中的方法相比，熵评判方法能更加准　确地度量网络节点之间的数据相关度，另外本文在　构造连通关联支配集时采用了一个能量感知的优先　级策略，能有效地均衡无线传感器网络的能量消耗．　ＥＥＣＤＳ算法首先通过评价随机变量的熵值来　判断ｇ跳网络节点间的数据相关性，然后在网络中　分布式地构造一个关联图，最后借助关联图的信息　构造一个连通关联支配集．ＥＥＣＤＳ算法能有效缩减　无线传感器网络的数据冗余，同时具有很好的能量　连通的，即集合Ｅ具有较大的势，因此相邻网络节　点采集的数据具有较大的相关性．　无线传感器网络所监测的现象大都是空间上分　散的，且符合高斯分布，这样的物理环境通常称为高　斯随机场．因此，我们假设　个网络节点采集的空间　数据向量ｘ具有高斯随机过程的特征，并且符合ｎ　维正态分布Ｇ　（　，Ｋ），则随机向量ｘ的概率密度函　数为　厂（Ｘ）一—＿＝＝＿二ｌ＿—一ｅ一专　卜　（１）　（￣／２　７ｃ）　ｊ　ＫＩ“　其中参数　为正态分布的均值，Ｋ一（是　）　为ｘ的　协方差矩阵，ｋ　，＝　。ｅ　ｃｄＰｉｊ，　∈｛１，２｝，ｄ　为网络节点　ｉ和　之问的距离，ｃ为调节系数．　协方差矩阵Ｋ刻画了网络空间数据的相关度，　节点之问的数据相关度会随着距离的增加而缩减．　为表示无线传感器网络中的数据相关性，本文　借鉴了文献Ｉ－９］中提出的关联图（ｃｏｒｒｅｌａｔｉｏｎ　ｇｒａｐｈ）　的概念．　定义１．　给定一个无线传感器网络，传感器节　点集合为Ｒ，则关联图定义为以Ｒ为顶点集合、以　Ｐ（尺）×Ｒ的一个子集为有向超边（ｈｙｐｅｒｅｄｇｅ）集合　的有向超图（ｈｙｐｅｒｇｒａｐｈ），其中Ｐ（Ｒ）是集合Ｒ的　幂集（ｐｏｗｅｒ　ｓｅｔ），该关联图用Ｇ　（Ｖ—Ｒ，Ｅ　Ｐ（Ｒ）×Ｒ）表示．　关联图Ｇ　中的一条边（ｗ，“），Ｕ　Ｗ表示节点　“感知的数据与集合ｗ中的节点感知的数据高度相　关，因此节点Ｕ的数据可以在一定的误差范围之内由　集合ｗ中的节点推算出，换言之，在给定集合ｗ中　节点感知的数据的基础上，节点Ｕ的数据是冗余的．　将集合ｗ定义为关联子集（ｃｏｒｒｅｌａｔｅｄ　ｓｕｂｓｅｔ），节点　“定义为关联节点（ｃｏｒｒｅｌａｔｅｄ　ｖｅｒｔｅｘ）．　下面在关联图的基础上，给出关联支配集　（ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ）的概念．　定义２．　关联支配集是图Ｇ（Ｖ，Ｅ）中的顶点集　合ＳＣＶ，满足对于任何顶点“Ｅ（　—Ｓ），至少存在　一个节点子集Ｗ　Ｓ，且（　，“）为关联图Ｇ　中的一　个有向超边．如果集合Ｓ的诱导子图是图Ｇ的一个　连通子图，则称ｓ为连通关联支配集（ｃｏｎｎｅｃｔｅｄ　１期　于瑞云等：无线传感器网络中基于熵评判的关联支配集构造算法　８９　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ）．　图论中的支配集（ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ）概念如定义３　所述．　定义３．　支配集是图Ｇ（　，Ｅ）中的顶点集合　Ｓ（二＝　，满足对于任何顶点　∈Ｖ，或者　∈Ｓ，或者口　与集合ｓ中至少一个顶点相邻．　与支配集的概念不同，在关联支配集中，非支配　集节点不一定要与支配集中的节点相邻，但是要确　保非支配集中的任何节点都与支配集中的某些节点　具有较高的相关度．相关度的度量方法将在第３节　中进行详细定义．　３　问题定义　基于条件熵评判的关联支配集构造算法　（ＥＥＣＤＳ）是在给定的无线传感器网络中根据关联　图结构来构造一个最小的连通关联支配集Ｃ，通过　收集集合Ｃ中节点感知的数据能够以较小的误差　复原网络中所有节点产生的数据．ＥＥＣＤＳ是通过减　少参与通信的节点数量来消除网络中冗余数据的传　输，能在保证网络数据完整性的基础上，有效地降低　网络节点的能量消耗．另外，ＥＥＣＤＳ算法还可以对　网络节点进行有效的休眠调度，均衡网络的能量　消耗．　在计算给定图Ｇ（Ｖ，Ｅ）的关联图Ｇ　时，我们采　用熵评判机制来判断超边的存在，具体地说，如果节　点Ｕ相对于集合ｗ中节点的条件熵小于一个应用　程序定义的阈值时，则关联图Ｇ　中就存在一个从　集合Ｗ至节点Ｕ的有向超边（ｗ，　）．　如第２节中所述，　个网络节点采集的数据　具有高斯随机过程的特征，并且符合ｎ维正态分布　Ｇ　（　，Ｋ），Ｋ为ｘ的协方差矩阵．集合　为集合ｘ　的一个子集，假设Ｗ一（Ｘ　Ｘ　…，Ｘ　。），其中ｉ　，　ｉ。，…，ｉ　∈｛１，２，…，ｎ），ｋ　为任意节点ＩＤ组合，　集合ｗ符合ｋ维正态分布Ｇ　（　，Ｋｗ），其协方差矩　阵为Ｋ　，ＫⅣ为协方差矩阵Ｋ中与ＩＤ值ｉ　，ｉ　，…，　ｉ　相关的子矩阵．　假设无线传感器网络节点感知的数据都以同样　的步长地进行量化分级，因此在这里将采用条　件微分熵进行节点数据相关度的评判．假设Ｗ一　（Ｘ　Ｘ¨…，Ｘ　。）是在较小的步长△下进行量　化分级得到的愚个离散的随机值，根据文献［１０］，　ｋ维正态分布Ｇ　（　，Ｋｗ）的微分熵为　１　ｈ（Ｇ　（　，Ｋｗ））一音ｌｏｇ（２ｈｅ）　ｆＫｌｗ　ｆ　（２）　该正态分布的联合熵近似为　Ｈ（　（　，Ｋｗ））≈＾（Ｇ　（　，Ｋｗ））一ｋｌｏｇｋ　１　＝＝＝￣　１ｏｇ（２ｎｅ）　Ｉ　Ｋｗ　Ｉ－－ｋ　ｌｏｇＡ（３）　则在给定集合ｗ节点的数据的基础上，节点　需要　传输的数据率Ｒ　即为节点“相对于集合ｗ的条件　熵，其值如式（４）所示，其中Ｗ　一ＷＵ｛Ｕ）：　Ｒ乱＝＝＝Ｈ（Ｕ，Ｗ）一Ｈ（Ｗ）　１　一一￣ｌｏｇ（２ｈｅ）　ＩＫⅣ，ｌ一（是＋１）ｌｏｇＡ一　，１　、　（寺ｌｏｇ（２　７ｃｅ）　ＩＫｗ　ｋ　ｌｏｇｋ）　１　一去（１ｏｇ（２ｎｅ）卜　ｆＫⅣ，Ｉ—ｌｏｇ（２ｔｅｅ）　ｌＫｗ｛）一　厶　ｌｏｇＡ　（４）　根据文献［－１０］，一个符合正态分布的连续随机　变量的微分熵为　１　ｈ（Ｇ（／ｘ，　。））一７。ｌｏｇ（２ｎｅａ　）　（５）　则节点　的离散熵的值为　１　Ｈ　一ｈ　一ｌｏｇＡ一９　－ｌｏｇ（２　ｒｒｅａ　）一ｌｏｇＡ　（６）　Ｈ　实际上为节点　传送感知数据的数据　率，所以当Ｒ　的值小于一个给定的阈值　Ｈ　，　一０　时，则可以判定节点“与节点集合ｗ高度相关，即　在超图Ｇ　中存在有向超边（Ｗ，“），其中参数　为　误差系数，由Ｒ　＜　Ｈ　可得　１　妻（１ｏｇ（２ｎｅ）　ＩＫⅣ，Ｉ—ｌｏｇ（２ｎｅ）　ＩＫｗ【）一ｌｏｇＡ＜　（寺ｌｏｇ（２　７ｃｅ　）一ｌｏｇＡ）　（７）　ＥＥＣＤＳ算法首先通过熵评判机制构造一个关　联图，然后在此基础上构造一个连通关联支配集．由　于在无线传感器网络中，节点问数据的相关度会随　着节点距离的增加而呈现指数衰减，所以在构造关　联图的时候，每个网络节点只判定与其ｇ跳范围内　节点集的幂集元素的相关性，ｇ通常取１～３，这能　够在很大程度上减少计算的开销．　４　算法描述　４．１，，ｌ跳邻居发现　为均衡无线传感器网络的能量消耗，算法引入　了一个能量感知的优先级策略，节点用二元组　（ｅｎｅｒｇｙ，ｉｄ）进行优先级分级，其中ｅｎｅｒｇｙ代表节　点的剩余能量值，ｉ　代表节点的ＩＤ值．　定义４．设节点“的优先级　一（ｅｎｅｒｇｙ　，ｉｄ　），　９０　计　算　机　学　报　节点　的优先级Ｐ　＝（ｅｎｅｒｇｙ　，ｉｄ　），则Ｐ　＞　，当　其仅当：　（１）ｅｎｅｒｇｙ　￣ｅｎｅｒｇｙ　或　（２）ｅｎｅｒｇｙ　一ｅｎｅｒｇｙ　且ｉｄ　ｄｉｄ　｛１，２，…，２”　ｓ　），令ｗ：Ｐ，，计算节点“与节点集合ｗ的　关联关系，如果满足式（７）的约束关系，则将集合　加入到　节点“的关联子集列表ＣＳＬｉｓｔ中；　２．每个关联节点计算完与其邻接的关联子集信息之　后，向其ｇ跳邻居节点广播ＣＳＮＯＴＩＦＹ消息，在消息中包含　显而易见，剩余能量值较低的节点将具有较高　的优先级，在ＥＥＣＤＳ算法中，此类节点将以较高的　优先级从连通关联支配集中移除，被移除的节点在　数据采集的时候不参与通信，因而减少了能量的消　该节点的ＩＤ和ＣＳＬｉｓｔ信息；　３．当一个节点收到ＣＳＮＯＴＩＦＹ消息时，如果该节点ＩＤ　出现在ＣＳＮＯＴＩＦＹ消息的ＣＳＬｉｓｔ中的记录中，则将这些记　录保存在关联节点列表ＣＶＩ　ｉｓｔ中，并在ＣＶＬｉｓｔ中保存相应　耗，延长了节点的生存时间．　在数据采集过程中消耗能量过多的节点会在下　一轮连通关联支配集构造的过程中获得较高的优先　级，因此能够均衡网络的能量消耗．　ＥＥＣＤＳ算法要求传感器网络节点能通过接收　ＧＰＳ信号或者其它定位方法确定各自的位置信息．　邻居发现阶段通过ｍ轮ＨＥＬＬＯ消息交换过　程让网络中的每个节点得到其ｎ２跳之内的所有邻　居节点的状态信息，包含节点的ＩＤ、剩余能量、位　置、着色（见４．３节）等信息．　在第１轮消息交换过程中，每个节点广播一个　ＨＥＬＬＯ消息，收到ＨＥＬＬＯ消息的节点将其一跳　邻居节点的信息保存在邻居列表里，直至它从所有　的一跳邻居处都收到ＨＥＬＬＯ消息．　在第ｉ∈［２，　］轮消息交换中，每个节点在广播　的ＨＥＬＬＯ消息中捎带它的ｉ一１跳邻居列表信息，　让该节点的直接邻居节点获取各自的ｉ跳邻居节点　的信息．　经过ｍ轮消息交换后，每个节点都会完成其ｍ　跳邻居节点信息的收集工作，这些邻居节点的信息　存储在邻居列表ＮＢＬｉｓｔ中．　如第３节中所述，每个网络节点只判定与其ｇ　跳范围内节点集的幂集元素的相关性，通常令ｇ∈　｛１，２，３），ｇ的取值要保证在生成关联图时让节点　获得足够的关联邻居节点的信息（见４．２节）．　在邻居发现阶段，通常设定跳数　∈｛２，３｝且　ｇ，ｍ的取值要保证在构造连通关联支配集时，　节点要有足够的邻居节点信息判断移除该节点后本　地网络的连通性（见４．３节）．　４．２生成关联图　ＥＥＣＤＳ算法通过本地算法构造一个关联图，在　关联图构造完成之后，每个节点成为关联图中的一　个关联节点，并且维护与该节点相邻接的关联子集　的信息以及该节点所在的关联子集的信息．　具体过程如下：　１．假设集合Ｎｇ（　）为节点　的ｇ跳开放邻居节点集，　对于Ｎ　（“）的幂集Ｐ（Ｎ　（“））中的每个集合元素Ｐ　，　∈　关联节点的信息．　经过上述过程，ＥＥＣＤＳ算法通过节点的分布式　计算和有限ｇ跳广播构造了一个关联图，每个节点　只掌握其与ｇ跳范围之内的邻居节点构成的局部　关联图信息，其中，与该节点邻接的关联子集的信息　存储在关联子集列表ＣＳＬｉｓｔ中，包含该节点的关联　子集的信息保存在关联节点列表ＣＶＬｉｓｔ中．　４．３构造连通关联支配集　连通关联支配集的构造过程是在连通的网络中　分布式移除一些关联节点，在移除这些关联节点的　同时保证网络的正常连通，直至构造一个较小的连　通关联支配集对整个网络进行关联支配．　ＥＥＣＤＳ算法采用一个着色过程（ｃｏｌｏｒｉｎｇ　ｐｒｏｃｅｓｓ）完成连通关联支配集的构造，具体实现过　程描述如下：　１．在起始阶段，每个节点都标记为灰色（ＧＲＡＹ）；　２．符合以下条件的灰色节点“将自己标记为白色　（ＷＨＩＴＥ）：　２．１．查看邻居列表ＮＢＬｉｓｔ，假设节点“所有优跳范围　之内的非白色节点集合为ｚ　Ｎ　（“），节点“的优先级　Ｐ　＞Ｐ　，Ｖｚ　∈Ｚ，五为灰色节点，并且集合ｚ的诱导子图是　连通的；　２．２．检查关联子集列表ＣＳＬｉｓｔ，在关联图Ｇ　中存在一　个超边（Ｗ，“），对于节点　∈Ｗ，或者节点　是黑色　（ＢＬＡＣＫ）的，或者节点　是灰色的且Ｐ　＜　，如果存在多个　满足条件的集合ｗ，选取其中具有最小势的集合；　２．３．检查关联节点列表ＣＶＬｉｓｔ，对于关联图Ｇ　中的　每一个超边（Ｕ，　），“∈Ｕ，节点　或者为白色，或者为黑色，　或者是灰色的且Ｐ　＜Ｐ　．　３．当灰色节点ｔＡ将自己标记为白色后，向其ｇ跳范围　内的邻居节点发送一个ｗＨＩＴＥＮ消息；　４．集合　中的灰色节点收到节点“发来的ｗＨＩＴＥＮ　消息后，将自己标记为黑色，然后发送一个ＢＬＡＣＫＥＮ　消息；　５．其它灰色节点收到一个ＷＨＩＴＥＮ消息或者一个　ＢＩ　ＡｃＫＥＮ消息后，更新邻居列表ＮＢＬｉｓｔ中发送消息节点　的着色信息，重新测试步２中的条件，如果满足条件，开始另　一轮着色过程；　６．当网络中的灰色节点全部被标记成黑色或白色，或　１期　于瑞云等：无线传感器网络中基于熵评判的关联支配集构造算法　者网络中没有符合步２中条件的灰色节点，算法结束．　ＥＥＣＤＳ算法执行完毕后，所有黑色节点和灰色　节点（如果存在）构成一个连通关联支配集．需要说　明的是，ＥＥＣＤＳ算法是采用分布式的节点退出机制　构造连通关联支配集，在算法执行的任何时刻，所得　到的关联支配集都是连通的．　５　性能评价　在本节中，我们将通过仿真来分析ＥＥＣＤＳ算　法的性能，为进行比较，同时对文献［９］中的算法（为　方便表述，用ＥＧＣＤ标记该算法）进行仿真分析．　５．１　协方差矩阵参数分析　为构造关联图，节点需要判断与其邻接的关联　子集是否满足式（７）的条件，式（７）中的协方差矩阵　日　元素ｋ　，一　ｅ　ｃｄｆｊ表示节点之间数据的相关度，　为　正态分布的方差，ｄ　，为网络节点ｉ和Ｊ之间的距离，　节点之间的数据相关度会随着距离的增加而缩减，口　的值通常取ｌ或２．　当　一１，　一２时，在系数ｃ取不同的值时，两个　节点的数据相关度随距离的变化情况如图１所示，Ｃ　值越大，在给定节点距离的情况下，两个节点之间的　数据相关度越低．　币点距禹／ｍ　图１　节点数据相关度随距离的变化　５．２连通关联支配集的大小　在本节中，仿真环境配置为：网络节点的通信半径　ｙ一３０ｍ，网络节点随机布置在１００ｍＸ１００ｍ的网络　区域内，节点数量分别取６０、８０、１００、１２０、１４０和１６０．　式（７）中的误差系数　一０．２，微分熵步长△一　２　，协方差矩阵参数　一１，　＝２．关联邻居跳数　ｇ一１，通信邻居跳数ｍ一２．　图２显示了在协方差矩阵参数Ｃ一０．０００１和　ｃ一０．０００５时ＥＥＣＤＳ算法获得的连通支配集大小　以及ＥＧＣＤ算法得到的连通支配集的大小．在网络　密集的情况下，ＥＥＣＤＳ算法具有较好的性能．当ｃ一　０．０００１时，ＥＥＣＤＳ算法获得较好的性能，但当Ｃ一　０．０００５时，在节点数为６Ｏ和８Ｏ时，网络中只有极　少数节点被缩减掉．　图２连通关联支配集的大小　ＥＧＣＤ算法采用一个简单的概率方法确定节点　的关联子集，在仿真中取关联百分比Ｐ一０．１，关联　距离　一２０　ｍ，当网络密度增大时，ＥＧＣＤ算法能获　得比ＥＥｃＤＳ更好的性能，但在网络稀疏时性能相　对较差．　图３显示了在上述配置情况下，节点数量为８Ｏ　时连通关联支配集的构造情况，图３（ａ）为网络的初　始连接，图３（ｂ）为得到的连通关联支配集，其中＊　（ｂ）连通关联支配集　图３　节点数为８Ｏ时连通关联支配集的构造　９２　计　算　机　学　报　２０１１年　号表示ＥＥＣＤＳ算法缩减掉的网络节点．　５．３各项参数对关联支配集大小的影响　５．３．１误差系数　的影响　在本小节中，仿真环境配置为：网络节点的通信　半径ｙ＝３０ｍ，网络节点随机布置在１００　ｍ×１００　ｍ　的网络区域内，节点数量分别取８０和１００．　微分熵步长Ａ一２　，协方差矩阵参数　一１，　一２，ｃ：０．０００２．关联邻居跳数ｇ一１，通信邻居跳　数　一２．　根据式（７），调整误差系数　将影响熵评判的结　果，增大　将构造一个更大的关联图，因而在构造连　通关联支配集的时候，节点将有更多的关联子集可　供选择，所以将缩减连通支配集的大小．如图４所　示，当误差系数　从０．１调整到０．６时，在８Ｏ个节　点的情况下，连通关联支配集的大小从５０降到３６，　当网络密度增加时，连通关联支配集大小占网络节　点数量的比率会随之降低，如图４中１００个网络节　点的情况，当　从Ｏ．１调整到Ｏ．６时，其连通支配集　大小从６１降到３９，当　一０．６时，比率值为３９　．　误差系数　图４误差系数　对关联支配集大小的影响　５．３．２微分熵步长值△的影响　在本小节中，仿真环境配置为：网络节点的通信　半径ｙ一３０　ｍ，网络节点随机布置在１００　ｍ　ｘ　１００　ＩＩ１　的网络区域内，网络节点数分别取８Ｏ和１００．　协方差矩阵参数　一１，　一２，ｆ一０．０００２，误差　系数　＝０．２，关联邻居跳数ｇ＝ｌ，通信邻居跳数　一２．　微分熵步长△分别取１／３２、１／１６、１／８、１／４、　１／２，图５显示了步长△对连通关联支配集大小的　影响．　如式（３）和式（６）所示，ｋ维正态分布的离散熵　为其微分熵与ｋ　ｌｏｇＡ的差值，因此，当△取值越大，　ｋ维正态分布变量的离散熵的值越小．由于　的取　值小于１，当步长△增大时，式（７）两端的值都减小，　图５　微分熵步长△对关联支配集大小的影响　但左端值的变化速度要高于右端，其结果是式（７）得　到满足的可能性增加了，也就是说，在构造关联图　时，节点的关联子集数量增多了，因此，获得最优连　通关联支配集的可能性随之提高，如图５所示，当步　长△增大时，组成连通关联支配集的节点数量呈现　出降低的趋势．　５．４算法的能耗特性　５．４．１平均能量消耗　本节的仿真配置为：网络节点的通信半径ｙ一　３０ｍ，网络节点随机布置在１００ｍ×１００ｍ的网络区　域内，节点数量分别取６０、８０、１００、１２０、１４０、１６０．　式（７）中的误差系数　一０．２，微分熵步长△一２＿　，　协方差矩阵参数　一１，　一２，ｆ一０．０００２．关联邻居　跳数ｇ一２，通信邻居跳数　一２．　假设仿真过程中发送和接收的数据包都具有同　样大小，能耗情况根据文献［１１］中的能耗模型给出，　网络节点发送数据包消耗１个单位的能量，接收数　据包消耗０．５个单位的能量，网络节点在空闲状态　下的能耗忽略不计．　ＥＥＣＤＳ算法的能耗主要包括在邻居发现阶段　和连通关联支配集构造阶段发送和接收消息所消耗　的能量以及在生成关联图阶段用于计算的能量开　销．构造关联图时，每个节点计算并比对ｇ跳开放　邻居节点集的幂集元素与其的相关度，该过程的算　法复杂度为Ｏ（ｎ。・２　），其中　为网络节点的ｇ跳开　放邻居节点集的势．对于密集网络，这个计算过程是　非常耗资源的，因此，在实际运算的过程中，每个节　点最多选取与其最相关的ｓ个节点（比如Ｓ一１２）进　行关联图的构造，假设　ｓ的网络节点生成关联图　所消耗的能量与发送１Ｏ个消息消耗的能量相等，则　对于ｎ＜ｓ的节点，生成关联图的能耗值等同于发送　ｌ０・（ｎ／ｓ）　２…个消息．　１期　于瑞云等：无线传感器网络中基于熵评判的关联支配集构造算法　ＥＧｃＤ算法的关联图构造过程的算法复杂度为　０（Ｋ　Ｌ　），其中Ｋ是为了计算相关度而收集的采样　个数，Ｌ为ｒａｎｋ值，并且Ｌ＜Ｋ，所以每个节点为计　算关联图而消耗的能量基本相同，假设均与发送１０　个消息所消耗的能量相等（文献［９］中假设与发送　４Ｏ个消息的能耗相等）．　此外，ＥＧＣＤ算法是通过收集邻近节点的采样　数据来判断与邻近节点的数据相关性，在开始构造　关联图之前，每个节点还需要广播收集到ｉ个采样　数据供其它节点进行数据相关性分析．　在不同的网络拓扑结构下连续运行ＥＥＣＤＳ算　法和ＥＧＣＤ算法各１ｏ次，图６显示了两种算法的　平均能量消耗情况，在每种网络配置下，ＥＥＣＤＳ算　法的节点平均消耗都要优于ＥＧＣＤ算法．　图６算法的平均能量消耗　５．４．２能量均衡特性　本节的仿真配置为：网络节点的通信半径ｙ一　３Ｏｍ，８０个网络节点随机布置在１００　ｒｌｌ×１００ｍ的网　络区域内．误差系数　一０．２，微分熵步长△一２　，　协方差矩阵参数　一１，　一２，ｒ－＿０．０００２．关联邻居　跳数ｇ＝＝＝２，通信邻居跳数　一２．　每个节点的初始能量值设为１４５０～１５００个单　位之间的随机值．在相同的网络拓扑结构下连续运　行ＥＥＣＤＳ算法和ＥＧＣＤ算法各５次，在每次执行　过程中，首先构造一个连通关联支配集，然后在此支　配集的基础上随机选择一个节点为根节点构造一个　树状通信结构，并在此通信树结构上运行一个简单　的查询应用程序１Ｏ次．该应用程序首先从根节点洪　泛一个ＱＵＥＲＹ请求消息，然后从每个节点沿着通　信树结构向根节点发回一个数据包．　仿真结束后，网络节点的能耗情况如图７所示．　从图７可以看出，ＥＥＣＤＳ算法具有很好的能量　均衡性，这是因为ＥＥＣＤＳ算法采用了能量感知的　耀　∞　藻　图７算法的能量均衡性　优先级机制，组成连通关联支配集的节点负责网络　数据的采集和传送，要消耗更多的能量，因而在下一　轮关联支配集的构造过程中将获得较高的优先级，　增大了从网络中移除的可能性．　ＥＥＣＤＳ算法的能量均衡特性对延长无线传感　器网络的生命周期起到了十分显著的作用．　６相关研究与本文结论　文献［１］主要研究单一输入的编码策略，提出了　两种编码方法：外编码和自编码．针对这两种方法，　分别提出了构造数据采集树的最优算法和近似最优　算法，目的是最小化在网络中传输的数据的加权比　特数．　文献Ｅ２］提出用数据采集节点跟踪网络节点的　相关性信息，当获得足够的节点相关信息，数据采集　节点通知各个网络节点进行数据编码的比特位数，　从而进行有效地冗余抑制．　文献［３—４］设计了两种编码策略，一种基于条件　熵，另一种基于Ｓｌｅｐｉａｎ—Ｗｏｌｆ编码模型［１　，算法研　究了在两种编码策略下，进行通信结构和节点数据　率分配的联合优化问题，从而在单汇聚节点的树状　通信结构中最小化网络数据传输的能量开销．　文献Ｅ５］考虑了以数据采集为背景的传感器网　络节点布置和通信结构的联合优化问题，目的是优　化布置传感器网络节点，使网络节点产生的数据能　在汇聚节点处以较小的失真率进行数据重建，同时　最小化网络通信的能量消耗．文献研究了在满足网　络最大失真和平均失真约束条件下的基于条件熵和　Ｓｌｅｐｉａｎ—ｗｏ１ｆ编码的算法设计．　文献Ｅ６］提出了一个随机树构造算法为单汇聚　节点的数据采集应用构造数据融合树，网络节点感　９４　计　算　机　学　报　知的数据在向汇聚节点传送的过程中，可以在中间　网络节点上进行数据融合，从而减少了在网络中传　输的数据量．该算法对于所有非降的凹聚合函数都　有很好的近似比．　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｆｏｕｎｄａｔｉｏｎｓ　ｏｆ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ（ＤＩＡＬＭ—　Ｐ０ＭＣ’０４）．Ｐｈｉｌａｄｅｌｐｈｉａ，ＰＡ，Ｕｎｉｔｅｄ　Ｓｔａｔｅｓ，２００４：６０—６６　［２］Ｃｈｏｕ　Ｊ，Ｐｅｔｒｏｖｉｃ　Ｄ，Ｋａｎｎａｎ　Ｒ．Ａ　ｄｉｓｔｒｉｂｕｔｅｄ　ａｎｄ　ａｄａｐｔｉｖｅ　ｓｉｇｎａｌ　ｐｒｏｃｅｓｓｉｎｇ　ａｐｐｒｏａｃｈ　ｔｏ　ｒｅｄｕｃｉｎｇ　ｅｎｅｒｇｙ　ｃｏｎｓｕｍｐｔｉｏｎ　ｉｎ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２２ｎｄ　Ａｎｎｕａｌ　Ｊｏｉｎｔ　Ｃｏｎ—　ｆｅｒｅｎｃｅ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｏｃｉｅｔｉｅｓ　在文献［７３中，为在传感器网络中构造进行高效　数据采集的数据融合树，作者提出了一个简单的随　机树构造算法，该算法在以栅格图方式布置的网络　中具有常数近似比．　（ＩＮＦｏＣｏＭ’０３）．Ｓａｎ　Ｆｒａｎｃｉｓｃｏ，ＣＡ，ＵＳＡ，２００３：ｌ０５４—　１０６２　［３］Ｃｒｉｓｔｅｓｃｕ　Ｒ，Ｖｅｔｔｅｒｌｉ　Ｍ．Ｐｏｗｅｒ　ｅｆｆｉｃｉｅｎｔ　ｇａｔｈｅｒｉｎｇ　ｏｆ　ｃｏｒｒｅｌａ—　ｔｅｄ　ｄａｔａ：Ｏｐｔｉｍｉｚａｔｉｏｎ，ｎｐ—ｃｏｍｐｌｅｔｅｎｅｓｓ　ａｎｄ　ｈｅｕｒｉｓｔｉｃｓ．ＳＩＧ—　ＭＯＢＩｌ　Ｅ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｒｅｖｉｅｗ，　文献Ｅｓ］根据传感器网络节点的空间相关度，研　究从网络中选取一部分节点向汇聚节点传输感知的　数据，以消除网络中的冗余数据．文献提出的算法采　用一个简单的本地算法选取一些簇头节点，然后选取　一些中间节点将簇头节点连通成一个最短路径树，在　树结构之外的节点将不参与数据采集的通信过程．　文献［９］先从邻近节点收集一定数量的采样数　据，然后根据这些采样数据判断与邻近节点的相关　度，并基于节点相关程度构造一个关联图．接着在关　联图的基础上构造一个连通关联支配集，关联支配　集之外的节点将从数据采集应用的通信结构中　移除．　文献［１３—１９］研究了在无线网络中构造连通支　配集的算法，但这些算法都是研究通用的连通支配　集构造策略，不是专门基于传感器网络背景的，因而　也没有考虑在无线传感器网络中进行数据冗余缩减　的问题．　文献［２ｏ一２２］是从路由的角度设计一些分布式算　法来鉴别在路由过程中节点的冗余性，也就是在满足　网络路由性能要求的前提下，可以在路由通信过程中　排除一些网络节点，这些节点可以被调度休眠，从而　节省网络的能量消耗．但这些策略只是考虑网络节点　的冗余，而没有考虑节点之间数据的相关性．　本文提出了一个基于熵评判的关联支配集构造　算法（ＥＥＣＤＳ），算法首先在网络中分布式构造一个　关联图，然后结合关联图的信息构造一个连通关联　支配集．通过收集关联支配集中节点感知的数据，能　够以较小的误差复原网络中所有节点产生的数据，　因此ＥＥＣＤＳ算法能在保证网络数据完整性的前提　下有效地缩减无线传感器网络的数据冗余，减少在　网络中传输的数据量，从而降低网络的能量消耗，延　长网络的生命周期．　参　考　文　献　［１］Ｖｏｎ　Ｒｉｅｋｅｎｂａｅｈ　Ｐ，Ｗａｔｔｅｎｈｏ［ｅｒ　Ｒ．Ｇａｔｈｅｒｉｎｇ　ｃｏｒｒｅｌａｔｅｄ　ｄａｔａ　ｉｎ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２００４　Ｊｏｉｎｔ　２００３，７（３）：３１—３２　［４］　Ｃｒｉｓｔｅｓｃｕ　Ｒ，Ｂｅｆｅｒｕｌｌ—Ｌｏｚａｎｏ　Ｂ，Ｖｅｔｔｅｒｌｉ　Ｍ．Ｏｎ　ｎｅｔｗｏｒｋ　ｃｏｒｒｅｌａｔｅｄ　ｄａｔａ　ｇａｔｈｅｒｉｎｇ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２３ｒｄ　Ａｎｎｕａｌ　Ｊｏｉｎｔ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　Ｓｏｃｉｅｔｉｅｓ（ＩＮＦｏＣｏＭ’０４）．Ｈｏｎｇ　Ｋｏｎｇ，Ｃｈｉｎａ，２００４：２５７１—　２５８２　ｒ５］　Ｇａｎｅｓａｎ　Ｄ，Ｃｒｉｓｔｅｓｃｕ　Ｒ，Ｂｅｆｅｒｕｌｌ—Ｌｏｚａｎｏ　Ｂ．Ｐｏｗｅｒ－ｅｆｆｉｃｉｅｎｔ　ｓｅｎｓｏｒ　ｐｌａｃｅｍｅｎｔ　ａｎｄ　ｔｒａｎｓｍｉｓｓｉｏｎ　ｓｔｒｕｃｔｕｒｅ　ｆｏｒ　ｄａｔａ　ｇａｔｈｅｒ—　ｉｎｇ　ｕｎｄｅｒ　ｄｉｓｔｏｒｔｉｏｎ　ｃｏｎｓｔｒａｉｎｔｓ／／Ｐｒ０ｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３ｒｄ　Ｉｎ—　ｔｅｒｎａｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｐｒｏｃｅｓｓｉｎｇ　ｉｎ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ（ＩＰＳＮ’０４）．Ｂｅｒｋｅｌｅｙ，ＣＡ，ＵＳＡ，２００４：１４２—１５０　［６］Ｇｏｅｌ　Ａ，Ｅｓｔｒｉｎ　Ｄ．Ｓｉｍｕｌｔａｎｅｏｕｓ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｏｒ　ｃｏｎｃａｖｅ　ｃｏｓｔｓ：Ｓｉｎｇｌｅ　ｓｉｎｋ　ａｇｇｒｅｇａｔｉｏｎ　ｏｒ　ｓｉｎｇｌｅ　ｓｏｕｒｃｅ　ｂｕｙ－ａｔ—ｂｕｌｋ．　Ａｌｇｏｒｉｔｈｍｉｃａ，２００５，４３（１—２）：５－１５　［７］　Ｅｎａｃｈｅｓｃｕ　Ｍ，Ｇｏｄ　Ａ，Ｇｏｖｉｎｄａｎ　Ｒ，Ｍｏｔｗａｎｉ　Ｒ．Ｓｃａｌｅ　ｆｒｅｅ　ａｇｇｒｅｇａｔｉｏｎ　ｉｎ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１　ｓｔ　Ｉｎ—　ｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ａｌｇｏｒｉｔｈｍｉｃ　Ａｓｐｅｃｔｓ　ｏｆ　Ｗｉｒｅｌｅｓｓ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ（Ａｌｇｏｓｅｎｓｏｒｓ’０４）．Ｔｕｒｋｕ，Ｆｉｎｌａｎｄ，２００４：　７１　８４　［８］Ｙｏｏｎ　ＳｕｎＨｅｅ，Ｓｈａｈａｂｉ　Ｃｙｒｕｓ．Ｅｘｐｌｏｉｔｉｎｇ　ｓｐａｔｉａｌ　ｃｏｒｒｅｌａｔｉｏｎ　ｔｏｗａｒｄｓ　ａｎ　ｅｎｅｒｇｙ　ｅｆｆｉｃｉｅｎｔ　ｃｌｕｓｔｅｒｅｄ　ａｇｇｒｅｇａｔｉｏｎ　ｔｅｃｈｎｉｑｕｅ　（ＣＡＧ）／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｃｏｍｍｕｎｉｃａｔ｛ｏｎｓ（ＩＣＣ’Ｏ５）．Ｓｅｏｕｌ，Ｓｏｕｔｈ　Ｋｏｖｅｒ，２００５：　３３０７　３３１３　［９］Ｇｕｐｔａ　Ｈ，Ｎａｖｄａ　Ｖ，Ｄａｓ　Ｓ，Ｃｈｏｗｄｈａｒｙ　Ｖ．Ｅｆｆｉｃｉｅｎｔ　ｇａｔｈｅｒ—　ｉｎｇ　ｏｆ　ｃｏｒｒｅｌａｔｅｄ　ｄａｔａ　ｉｎ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ．ＡＣＭ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｓｅｎｓｏｒ　Ｎｅｔｗｏｒｋｓ，２００８，４（１）：ｌ－３１　［１０］Ｃｏｖｅｒ　Ｔ　Ｍ，Ｔｈｏｍａｓ　Ｊ　Ａ．Ｅｌｅｍｅｎｔｓ　ｏｆ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ．　Ｎｅｗ　Ｙｏｒｋ：Ｊｏｈｎ　Ｗｉｌｅｙ　ａｎｄ　Ｓｏｎｓ，Ｉｎｃ．，１９９１　［１１］Ｋｕｂｉｓｃｈ　Ｍ，Ｋａｒｌ　Ｈ，ｗｏｌｉｓｚ　Ａ，Ｚｈｏｎｇ　Ｌ　Ｃ　ｅｔ　ａ１．Ｄｉｓｔｒｉｂｕｔｅｄ　ａｌｇｏｒｉｔｈｍｓ　ｆｏｒ　ｔｒａｎｓｍｉｓｓｉｏｎ　ｐｏｗｅｒ　ｃｏｎｔｒｏｌ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ／／Ｐｒ０ｃｅｅ　ｄｉｎｇｓ　ｏｆ　ｔｈｅ　２００３　ＩＥＥＥ　Ｗｉｒｅｌｅｓｓ　Ｃｏｍｍｕｎｉ—　ｃａｔｉｏｎｓ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ　Ｃｏｎｆｅｒｅｎｃｅ（ＷＣＮＣ’０３）．Ｎｅｗ　Ｏｒｌｅ—　ａｎｓ，ＬＡ，ＵＳＡ，２００３：５５８—５６３　［１２３　Ｓｌｅｐｉａｎ　Ｄ，Ｗｏｌｆ　Ｊ　Ｋ．Ｎｏｉｓｅｌｅｓｓ　ｃｏｄｉｎｇ　ｏｆ　ｃｏｒｒｅｌａｔｅｄ　ｉｎｆｏｒｍａ—　ｔｉｏｎ　ｓｏｕｒｃｅｓ．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｉｎｆｏｒｍａｔｉｏｎ　Ｔｈｅｏｒｙ，　１９７３，ＩＴ　１９（４）：４７１—４８０　［１３］Ｓｔｏｊｍｅｎｏｖｉｃ　Ｉ，Ｓｅｄｄｉｇｈ　Ｍ，Ｚｕｎｉｃ　Ｊ．Ｄｏｍｉｎａｔｉｎｇ　ｓｅｔｓ　ａｎｄ　ｎｅｉｇｈｂｏｒ　ｅｌｉｍｉｎａｔｉｏｎ－ｂａｓｅｄ　ｂｒｏａｄｃａｓｔｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍｓ，２００２，１３（１）：１４—２５　［１４］Ａｄｊｉｈ　Ｃ，Ｊａｃｑｕｅｔ　Ｐ，Ｖｉｅｎｎｏｔ　Ｌ．Ｃｏｍｐｕｔｉｎｇ　ｃｏｎｎｅｃｔｅｄ　ｄｏｍｉ—　ｎａｔｅｄ　ｓｅｔｓ　ｗｉｔｈ　ｍｕｈｉｐｏｉｎｔ　ｒｅｌａｙｓ．Ａｄ　Ｈｏｃ　ａｎｄ　Ｓｅｎｓｏｒ　Ｎｅｔ—　ｗｏｒｋｓ，２００５，１（１）：２７－３９　于瑞云等：无线传感器网络中基于熵评判的关联支配集构造算法　９５　［１５］　Ｗｕ　Ｊ，　Ｈ．Ｏｎ　ｃａｌｃｕｌａｔｉｎｇ　ｃｏｎｎｅｃｔｅｄ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｆｏｒ　ｅｆ　ｆｉｃｉｅｎｔ　ｒｏｕｔｉｎｇ　ｉｎ　ａｄ　ｈｏｃ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　３ｒｄ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｗｏｒｋｓｈｏｐ　ｏｎ　Ｄｉｓｃｒｅｔｅ　Ａｌｇｏｒｉｔｈｍｓ　ａｎｄ　Ｍｅｔｈｏｄｓ　ｆｏｒ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ．　Ｓｅａｔｔｌｅ，Ｗａｓｈｉｎｇｔｏｎ，Ｕｎｉｔｅｄ　Ｓｔａｔｅｓ，１９９９　［１６］　Ｄａｉ　Ｆ，Ｗｕ　Ｊ．Ａｎ　ｅｘｔｅｎｄｅｄ　ｌｏｃａｌｉｚｅｄ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｃｏｎｎｅｃｔｅｄ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｆｏｒｍａｔｉｏｎ　１ｎ　ａｄ　ｈｏｃ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ．ＩＥＥＥ　Ｔｒａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｐａｒａｌｌｅ１　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｓｙｓｔｅｍｓ，２００４，ｉ５　（１０）：９０８　９２０　［１　７］　Ｗａｎ　Ｐｅｎｇ—Ｊｕｎ，Ａｌｚｏｕｂｉ　Ｋ　Ｍ，Ｆｒｉｅｄｅｒ　Ｏ．Ｄｉｓｔｒｉｂｕｔｅｄ　ｃｏｎ—　ｓｔｒｕｃｔｉｏｎ　ｏｆ　ｃｏｎｎｅｃｔｅｄ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｉｎ　ｗｉｒｅｌｅｓｓ　ａｄ　ｈｏｃ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　２　１　ｓｔ　Ａｎｎｕａｌ　Ｊｏｉｎｔ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｆ　ｔｈｅ　ＩＥＥＥ　Ｃｏｍｐｕｔｅｒ　ａｎｄ　Ｃｏｍｍｕｎｉｅａｔｉｏｎｓ　Ｓｏｃｉｅｔｉｅｓ　（ＩＮＦＯＣＯＭ’Ｏ２）．Ｎｅｗ　Ｙｏｒｋ，ＮＹ，ＵＳＡ，２００２：１５９７　１６０４　［１８］　Ｄａｉ　Ｆ，Ｗｕ　Ｊ．Ｏｎ　ｃｏｎｓｔｒｕｃｔｉｎｇ　ｃｏｎｎｅｃｔｅｄ　ｋ—ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　１９ｔｈ　ＩＥＥＥ　Ｉｎｔｅｒｎａ—　ｔｉｏｎａｌ　Ｓｙｍｐｏｓｉｕｍ　ｏｎ　Ｐａｒａｌｌｅｌ　ａｎｄ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｐｒｏｃｅｓｓｉｎｇ．　Ｄｅｎｖｅｒ，ＣＯ，ＵＳＡ，２００５：１０　ＹＵ　Ｒｕｉ—Ｙｕｎ，ｂｏｒｎ　ｉｎ　１９７４，Ｐｈ．Ｄ．，　ｌｅｃｔｕｒｅｒ．Ｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ｗｉｒｅｌｅｓｓ　ａｄ—ｈｏｃ　ｃｏｍｍｕｎｉｃａｔｉｏｎ，ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ，ｍｕｌｔｉ—ｓｅｎｓｏｒ　ｄａｔａ　ｆｕ—　ｓｉｏｎ，ｅｔｃ．　Ｂａｃｋｇｒｏｕｎｄ　Ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ　ａｒｅ　ｄａｔａ—ｏｒｉｅｎｔｅｄ，ｗｈｏｓｅ　ｍａｉｎ　ｔａｓｋ　ｉｓ　ｄａｔａ　ｐｒｏｃｅｓｓｉｎｇ，ｉｎｃｌｕｄｉｎｇ　ｓｅｎｓｉｎｇ，ｄａｔａ　ｇａｔｈｅｒｉｎｇ，　ｔｒａｎｓｍｉｓｓｉｏｎ，ｃｏｍｐｒｅｓｓ，ａｇｇｒｅｇａｔｉｏｎ，ａｎｄ　ｓｏ　ｏｎ．Ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ　ａｒｅ　ｕｓｕａｌｌｙ　ｄｅｎｓｅｌｙ　ｄｅｐｌｏｙｅｄ　ｉｎ　ａ　ｎｅｔｗｏｒｋ　ａｒｅａ，ａｎｄ　ｇｅｎｅｒａｔｅ　ａ　ｇｒｅａｔ　ｄｅａｌ　ｏｆ　ｄａｔａ．Ｍｏｒｅｏｖｅｒ，ｔｈｅ　ｄａｉａ　ｓｅｎｓｅｄ　ｂｙ　ｎｅｉｇｈｂｏｒｉｎｇ　ｎｏｄｅｓ　ｉｓ　ｈｉｇｈｌｙ　ｃｏｒｒｅｌａｔｅｄ．Ｔｈｅｓｅ　ａｌｌ　ｉｍｐｏｓｅ　ｇｒｅａｔ　ｃｈａｌｌｅｎｇｅｓ　ｏｎ　ｔｈｅ　ｄｅｓｉｇｎ　ｏｆ　ｄａｔａ　ｇａｔｈｅｒｉｎｇ　ａｌｇｏ—　ｒｉｔｈｍｓ．Ｓｉｎｃｅ　ｔｈｅ　ｓｅｎｓｏｒ　ｎｏｄｅｓ　ａｒｅ　ｐｏｗｅｒ—ｃｏｎｓｔｒａｉｎｅｄ，ｔｒａｎｓ—　ｆｅｒｒｉｎｇ　ｌａｒｇｅ　ａｍｏｕｎｔｓ　ｏｆ　ｄａｔａ　ｄｅｆｉｎｉｔｅｌｙ　ｗｉｌｌ　ｓｈｏｒｔｅｎ　ｔｈｅ　ｌｉｆｅ—　ｔｉｍｅ　ｏｆ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ．Ｔｈｅｒｅｆｏｒｅ，ｔｈｅ　ｎｅｔｗｏｒｋ　ｐｅｒｆｏｒｍ—　ａｎｃｅ　ｏｎ　ｅｎｅｒｇｙ　ｃｏｎｓｕｍｐｔｉｏｎ　ａｎｄ　ｓｔａｂｉｌｉｔｙ　ｃｏｕｌｄ　ｂｅ　ｉｍｐｒｏｖｅｄ　ｔｈｒｏｕｇｈ　ｄａｔａ　ｒｅｄｕｎｄａｎｃｙ　ｒｅｍｏｖａ１．　Ｉｎ　ｔｈｉｓ　ｐａｐｅｒ，ａｎ　ａｌｇｏｒｉｔｈｍ　ｎａｍｅｄ　ｔｈｅ　ｅｎｔｒｏｐｙ　ｅｖａｌｕａ—　ｔｉｏｎ　ｆｏｒ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｃｏｎｓｔｒｕｃｔｉｏｎ（ＥＥＣＤＳ）ｉｓ　ｐｒｅｓｅｎｔｅｄ．Ｔｈｅ　ＥＥＣＤＳ　ａｌｇｏｒｉｔｈｍ　ｅｘｐｌｏｉｔｓ　ｔｈｅ　ｃｏｎｃｅｐｔ　ｏｆ　ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ．Ｉｔ　ｆｉｒｓｔ　ｄｅｔｅｒｍｉｎｅｓ　ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｂｅｔｗｅｅｎ　ｓｅｎｓｏｒ　ｎｏｄｅｓ　ｂｙ　ｅｖａｌｕａｔｉｎｇ　ｔｈｅ　ｅｎｔｒｏｐｙ　ｏｆ　ｒａｎｄｏｍ　ｖａｒｉａｂｌｅｓ，ａｎｄ　ｔｈｅｎ　ｄｉｓｔｒｉｂｕｔｉｖｅｌｙ　ｇｅｎｅｒａｔｅｓ　ａ　ｃｏｒｒｅｌａｔｉｏｎ　ｇｒａｐｈ．Ａｔ　ｌａｓｔ，ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｃｏｎｓｔｒｕｃｔｓ　ａ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉ—　ｎａｔｉｎｇ　ｓｅｔ　ｕｓｉｎｇ　ｔｈｅ　ｉｎｆｏｒｍａｔｉｏｎ　ｏｆ　ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｇｒａｐｈ．Ｔｈｅ　ＥＥＣＤＳ　ａｌｇｏｒｉｔｈｍ　ｉｓ　ｖｅｒｙ　ｅｆｆｉｃｉｅｎｔ　ｏｎ　ｒｅｄｕｃｉｎｇ　ｄａｔａ　ｒｅｄｕｎｄａｎ—　ｃｙ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ，ａｎｄ　ｐｅｒｆｏｒｍｓ　ｗｅｌ１　ｏｎ　ｅｎｅｒｇｙ　ｂａｌａｎｃｅ　ａｎｄ　ｓｃａｌａｂｉｌｉｔｙ．　［１９］　Ｔｈａｉ　Ｍ　Ｔ，Ｚｈａｎｇ　Ｎ，Ｒａｖｉ　Ｔ，Ｘｕ　Ｘ．Ｏｎ　ａｐｐｒｏｘｉｍａｔｉｏｎ　ａｌｇｏ—　ｒｉｔｈｍｓ　ｏｆ　ｃｏｎｎｅｃｔｅｄ　ｍ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔｓ　ｉｎ　ｄｉｓｋ　ｇｒａｐｈｓ．　Ｔｈｅｏｒｅｔｉｃａｌ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，２００７，３８５（１　３）：４９—５９　［２Ｏ］　Ｃｈｅｎ　Ｂ，Ｊａｍｉｅｓｏｎ　Ｋ，Ｂａｌａｋｒｉｓｈｎａｎ　Ｈ，Ｍｏｒｒｉｓ　Ｒ．Ｓｐａｎ：Ａｎ　ｅｎｅｒｇｙ—　ｅｆｆｉｃｉｅｎｔ　ｃｏｏｒｄｉｎａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｆｏｒ　ｔｏｐｏｌｏｇｙ　ｍａｉｎｔｅ——　ｎａｎｃｅ　ｉｎ　ａｄ　ｈｏｃ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄｉｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　Ａｎｎｕａｌ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔｗｏｒｋｉｎｇ（ＭｏｂｉＣｏｍ’０１）．Ｒｏｍｅ，Ｉｔａｌｙ，２００Ｉ　［２１３　Ｘｕ　Ｙ，Ｈｅｉｄｅｍａｎｎ　Ｊ，Ｅｓｔｒｉｎ　Ｄ．Ｇｅｏｇｒａｐｈｙ　ｉｎｆｏｒｍｅｄ　ｅｎｅｒｇｙ　ｃｏｎｓｅｒｖａｔｉｏｎ　ｆｏｒ　ａｄ　ｈｏｃ　ｒｏｕｔｉｎｇ／／Ｐｒ。ｃｅｅ出ｎｇｓ　ｏｆ　ｔｈｅ　７ｔｈ　Ａｎ—　ｎｕａｌ　Ｉｎｔｅｒｎａｔｉｏｎａ１　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｍｏｂｉｌｅ　Ｃｏｍｐｕｔｉｎｇ　ａｎｄ　Ｎｅｔ—　ｗｏｒｋｉｎｇ（ＭｏｂｉＣｏｍ’０１）．Ｒｏｍｅ，２００１：７０—８４　Ｅ２２］　Ｙｅ　Ｆ，Ｚｈｏｎｇ　Ｇ，Ｃｈｅｎｇ　Ｊ，Ｌｕ　Ｓ　ｅｔ　ａ１．Ｐｅａｓ：Ａ　ｒｏｂｕｓｔ　ｅｎｅｒｇｙ　ｃｏｎｓｅｒｖｉｎｇ　ｐｒｏｔｏｃｏｌ　ｆｏｒ　ｌｏｎｇ—。ｌｉｖｅｄ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ／／Ｐｒｏｃｅｅｄ——　ｉｎｇｓ　ｏｆ　ｔｈｅ　Ｉｎｔｅｒｎａｔｉｏｎａｌ　Ｃｏｎｆｅｒｅｎｃｅ　ｏｎ　Ｄｉｓｔｒｉｂｕｔｅｄ　Ｃｏｍｐｕ—　ｔｉｎｇ　Ｓｙｓｔｅｍｓ（ＩＣＤＣＳ’０３）．Ｐｒｏｖｉｄｅｎｃｅ，ＲＩ，Ｕｎｉｔｅｄ　Ｓｔａｔｅｓ，　２００３．２８—３７　ＷＡＮＧ　Ｘｉｎｇ－Ｗｅｉ，ｂｏｒｎ　ｉｎ　１　９６８，Ｐｈ．Ｄ．，ｐｒｏｆｅｓｓｏｒ，　Ｐｈ．Ｄ．ｓｕｐｅｒｖｉｓｏｒ．Ｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ｉｎｃｌｕｄｅ　ＮＧＩ，ｍｏ—　ｂｉｌｅ　ｗｉｒｅｌｅｓｓ　Ｉｎｔｅｒｎｅｔ，ＩＰ／ＤＷＤＭ　ｏｐｔｉｃａｌ　Ｉｎｔｅｒｎｅｔ，ｅｔｃ．　ＬＩＵ　Ｙｏｎｇ—Ｈｅ，ｂｏｒｎ　ｉｎ　１　９　７４，Ｐｈ．Ｄ．，ａｓｓｏｃｉａｔｅ　ｐｒｏｆｅｓ—　ｓｏｒ．Ｈｉｓ　ｒｅｓｅａｒｃｈ　ｉｎｔｅｒｅｓｔｓ　ａｒｅ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｉｎｇ，ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ，ｓｅｃｕｒｉｔｙ，ａｎｄ　ｓｙｓｔｅｍ　ｉｎｔｅｇｒａｔｉｏｎ．　Ｔｈｉｓ　ｗｏｒｋ　ｉｓ　ｓｕｐｐｏｒｔｅｄ　ｂｙ　ｔｈｅ　Ｎａｔｉｏｎａｌ　Ｎａｔｕｒａ１　Ｓｃｉｅｎｃｅ　Ｆｏｕｎｄａｔｉｏｎ　ｏｆ　Ｃｈｉｎａ　ｕｎｄｅｒ　ｇｒａｎｔ　Ｎｏｓ．６１０７０１６２，７１０７１０２８，　６０８０２０２３　ａｎｄ　７０９３１００１；ｔｈｅ　Ｓｐｅｃｉａｌｉｚｅｄ　Ｒｅｓｅａｒｃｈ　Ｆｕｎｄ　ｆｏｒ　ｔｈｅ　Ｄｏｃｔｏｒａｌ　Ｐｒｏｇｒａｍ　ｏｆ　Ｈｉｇｈｅｒ　Ｅｄｕｃａｔｉｏｎ　ｕｎｄｅｒ　ｇｒａｎｔ　Ｎｏｓ．２０１０００４２１１００２５　ａｎｄ　２００７０１４５０１７；ｔｈｅ　Ｆｕｎｄａｍｅｎｔａｌ　Ｒｅｓｅａｒｃｈ　Ｆｕｎｄｓ　ｆｏｒ　ｔｈｅ　Ｃｅｎｔｒａｌ　Ｕｎｉｖｅｒｓｉｔｉｅｓ　ｕｎｄｅｒ　ｇｒａｎｔ　Ｎｏｓ．Ｎ０９０５０４００３，Ｎ０９０５０４００６　ａｎｄ　Ｎ１００４１７００１；ｔｈｅ　Ｄｏｃ—　ｔｏｒａ１　Ｓｃｉｅｎｔｉｆｉｃ　Ｒｅｓｅａｒｃｈ　Ｆｕｎｄ　ｏｆ　Ｌｉａｏｎｉｎｇ　Ｐｒｏｖｉｎｃｅ　ｕｎｄｅｒ　ｇｒａｎｔ　Ｎｏ．２０１０１０４０．　Ｏｍｅ　ｏｆ　ｍａｉｎ　ｔａｓｋｓ　ｏｆ　ｔｈｅ　ａｂｏｖｅ　ｍｅｎｔｉｏｎｅｄ　ｐｒｏｊｅｃｔｓ　ｉｓ　ｖｉｒ—　ｔｕａｌ　ｂａｃｋｂｏｎｅ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ｉｎ　ｗｉｒｅｌｅｓｓ　ｎｅｔｗｏｒｋｓ．Ｓｏｍｅ　ｐｕｂ—　ｌｉｓｈｅｄ　ｐａｐｅｒｓ　ｗｅｒｅ　ｆｏｃｕｓｉｎｇ　ｏｎ　ｃｏｎｎｅｃｔｅｄ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｃｏｎ—　ｓｔｒｕｃｔｉｏｎ，ａｎｄ　ｇｅｎｅｒａｔｉｎｇ　ｃｏｎｎｅｃｔｅｄ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔｓ　ａｓ　ｂａｃｋ—　ｂｏｎｅｓ　ｆｏｒ　ｒｏｕｔｉｎｇ，ｄａｔａ　ｃｏｌｌｅｃｔｉｏｎ，ｅｔｃ．　Ｔｈｉｓ　ｐａｐｅｒ　ｈｉｇｈｌｙ　ａｄｄｒｅｓｓｅｓ　ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｆａｃｔ　ｏｆ　ｗｉｒｅ一　１ｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ，ａｎｄ　ｐｒｏｐｏｓｅｓ　ａ　ｃｏｎｎｅｃｔｅｄ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉｎａｔｉｎｇ　ｓｅｔ　ｃｏｎｓｔｒｕｃｔｉｏｎ　ａｌｇｏｒｉｔｈｍ．Ｔｈｅ　ｃｏｒｒｅｌａｔｉｏｎ　ｄｏｍｉ—　ｎａｔｉｎｇ　ｓｅｔ　ｉｓ　ｕｓｅｄ　ｆｏｒ　ｄａｔａ　ｒｅｄｕｎｄａｎｃｙ　ｒｅｍｏｖａｌ，ａｎｄ　ｄａｔａ　ｇａｔｈｅｒｅｄ　ｆｒｏｍ　ｔｈｅ　ｓｅｔ　ｃｏｕｌｄ　ｒｅｃｏｖｅｒ　ｔｈｅ　ｎｅｔｗｏｒｋ　ｄａｔａ　ｗｉｔｈｉｎ　ａ　ｐｒｅｄｅｆｉｎｅｄ　ｅｒｒｏｒ　ｂｏｕｎｄ．Ｔｈｅ　ｅｎｔｒｏｐｙ　ｅｖａｌｕａｔｉｏｎ　ｍｅｔｈｏｄ　ｅｘ—　ｐｌｏｉｔｅｄ　ｉｎ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｃａｎ　ｌｅｖｅｒａｇｅ　ｄａｔａ　ｃｏｒｒｅｌａｔｉｏｎ　ｗｅｌｌ，　ａｎｄ　ｈｅｎｃｅ　ｇｕａｒａｎｔｅｅ　ｔｈｅ　ｅｆｆｉｃｉｅｎｃｙ　ｏｆ　ｄａｔａ　ｒｅｄｕｎｄａｎｃｙ　ｒｅｍｏｖ—　ａ】ｉｎ　ｗｊｔｅｌｅｓｓ　ｓｅｎｓｏｒ　ｎｅｔｗｏｒｋｓ．