WMSNs多成员集群形成算法及节点调度

郑惠月，冯秀芳

（太原理工大学 计算机科学与技术学院，山西 太原030024）

0 引 言

对于 无 线 多 媒 体 传 感 器 网 络［1－6］（wireless multimedia sensor networks，WMSNs）中 的 节 能 问 题，Alaei 等 在WMSNs中提出了一种分簇机制 （即单成员集群），其目的是创建多媒体节点间的协作能力以达到延长网络生命周期的目的［7］。Kibrewerk使用机器学习算法自组织映射来减少传输信息量，达到延长网络生命周期的目的［8］；文献 ［9］提出了一种多重簇头的无线传感器网络体系结构和一种基于节能和高效的路由协议，二者相互配合，在满足实时数据的端对端延迟要求并确保最大化非实时数据的吞吐量的基础上，降低了网络的能耗提高了网络的效率；文献 ［10］提出了一种基于博弈论的分布式多信道分配机制，改善了在不同信道条件下的网络性能参数，从而降低能耗；文献［11］提出了一种对无线传感器网络覆盖质量与节点休眠之间权衡关系的优化策略，并采用粒子群算法寻求最优组合，使网络综合性能得到了很大的提升。

由于无线多媒体传感器网络中，尤其是视频传感器，其传感器节点的感知区域受 “视角”的限制，并非一个完整的圆形区域，因此本文采用有向感知模型，即方向可调感知模型。在此基础上针对单成员集群算法 （single－membership clustering algorithm，SCA）不存在集群间相互协作，从而造成数据冗余和能量浪费的缺点，提出了一种多成 员 集 群 算 法 （multi－membership clustering algorithm，MCA），通过集群间的协作和节点调度功能来延长节点生命周期，减少采集信息以及处理、传输数据的冗余，降低能耗，延长整个网络生命周期。

1 有向感知模型

在无线多媒体传感器网络中，其传感器节点具有方向性和视角，所以节点的感知范围是一个以节点为中心、感知距离为半径的扇形区域。本文采用如图1所示的有向感知模型。该模型可用一个四元组 （P，R，珗v，α）表示。P（x，y）表示有向传感器节点位置的坐标；R 表示节点感知半径；珗v 表示节点的主感知方向；2α为视角范围。当α＝π时，是有向感知模型的一个特例，为全向感知模型。

图1 有向感知模型

目标P1被有向传感器节点覆盖的条件是：

2 多成员集群形成算法

在SCA 算法中，每一个节点只能属于一个集群，从而不存在集群间的合作，因而可能出现数据冗余的现象。为此，采用MCA 算法，即一个节点可以属于多个集群，集群之间有公共节点，这样集群间可进行相互协作，通过统一调度，可以降低数据冗余，节约能量，提高网络性能。

在对集群算法进行描述前，首先给出一些相关定义，如下所示。

定义1 簇头：在集群中作为判断一个节点是否属于本集群的参照节点，其它节点通过与其比较感知区域重叠度来确定是否属于这个集群。

定义2 集群规模因子 （γ）：感知区域重叠度的阈值，即一个节点作为集群中成员与簇头的最小重叠度，用来判断一个节点是否属于该集群。集群规模因子在集群算法开始执行时被设置为一个定值，具体大小根据不同的应用需求来确定。

定义3 节点重叠度 （η）：是指与这个节点的感知重叠面积达到集群规模因子 （γ）的节点的数量。

2.1 MCA算法总体思想

在无线多媒体传感器网络监测区域内随机布置n个节点，其中每个节点都能够确定自己的位置和方向，并在网络部署完成后向汇聚节点发送自己的方位及状态信息。首先根据具体的应用需求设置集群规模因子γ，然后从节点列表中找出一个还没有集群的节点作为簇头建立一个新的集群，网络中所有的节点都在新集群被建立的时候与新集群簇头节点进行计算测试能否成为其成员。当一个节点与簇头节点感知区域的重叠面积百分比大于集群规模因子γ时，其即成为该集群的成员。如果一个节点经计算属于多个集群，则将该节点加入其所属的所有集群。

由于一个节点可能属于多个集群，所以集群可能出现相交的情况。因此，在节点调度的时候，需要根据节点是否为公共节点、节点的剩余电量和节点前一阶段的工作状态来确定节点是否被选作簇头，防止某个节点因被频繁选作簇头而使能量快速耗光而提前结束工作。然后簇头调度集群内各个节点轮流工作，减少采集、传输和处理信息的冗余，节约能量，从而延长网络的生存周期。

2.2 MCA算法实现

在WMSNs监测区域内随机部署n个传感器节点，用集合S＝ ｛S1，S2，S3，…，Sn｝来表示，其中每个节点都能够确定自己的位置和方向。

状态向量SV 表示每个节点的状态，其中0 代表未集群；1代表已集群；2代表簇头；3代表共同节点。

SV 初值为＜0，…，0＞。

K 代表传感器节点的标号。

算法终止条件：状态向量SV 中不存在0状态。

多成员集群算法 （MCA）具体描述见表1。

3 节点调度

为了减少网络中采集、传输和处理信息的冗余，节约能量，延长网络的生存周期。本文采用了一种专门针对多成员集群算法设计的调度算法，由于多成员集群允许集群重叠，所以集群内和集群间都可进行协作，将此调度方法称为多成员集群调度 （multi－membership clustering scheduling，MCS）。MCS的主要思想如下：为了防止网络中某个节点因被频繁激活而使能量快速耗光而提前结束工作，需要根据一个节点是否为公共节点、节点的剩余电量和节点前一阶段的工作状态来综合选取节点来轮流工作，所以需要为所有节点设立一个优先级，根据优先级的高低来选择节点。在这里设立了两类优先级，即第一优先级PL1 和第二优先级PL2，并定义对于每个节点Si而言，其第一优先级与第二优先级之和决定了这个节点在被选作监视节点过程中的总优先级Pi。即

第一优先级PL1 的目的在于选择剩余能量尽量多，同时所属集群尽量多的节点，这样的节点由于剩余电量多，就可以更多次的完成监测任务，同时由于隶属度高，在其工作期间就可以有更多的节点处于休眠状态。第一优先级在每轮监测开始前确定，是一个静态的值，其定义为

表1 多成员集群算法

式中：ERi——节点Si当前剩余能量，EQi——在一个监测周期内若节点Si活动所消耗的能量，ERi／EQi——节点Si在当前剩余能量的情况下能为整个网络工作的次数，Wi——节点Si的隶属度。

第二优先级PL2 的目的是为了避免选择在连续的监测周期内监测同一区域的节点，同时希望在当前监测周期选择与上个监测周期监测节点来自不同集群的节点。所有节点Si的第二优先级PL2 初始均为0，即：＝0。

第二优先级PL2 在每轮监测周期内随着监测节点的选择而变化，当一个节点被选择为当前监测周期的监测节点后，其第二优先级便降低避免下回合再选择它，同时，与其在同一集群的其它节点的第二优先级也降低，避免下回合选择与上回合监测同一区域的节点，即：＝－1。

第一优先级与第二优先级合作共同确立节点的优先级，通过优先级来调度网络中的节点。

4 仿真实验

（1）集群规模因子γ对集群规模和集群数目的影响：本实验采用Matlab7.0实现，实验中假设所有的传感器节点都是同构的，即传感器节点参数规模相同。在1000×1000m2的监测区域内，部署感知半径为100m、传感夹角为45°的传感器节点。图2和图3通过改变传感器节点密度进行系统的性能分析。

图2和图3分别显示了在不同的部署密度下，集群数目和集群规模与集群规模因子γ的关系。从图3可以看出随着集群规模因子γ的增加，集群数目也随之增加，且节点部署密度越大，集群数目增长的越快。从图4可以看出随着集群规模因子γ的增大，集群规模逐步降低，且节点部署密度越大，集群规模降低的越明显。

图2 集群数目与集群规模因子的关系

图3 集群规模与集群规模因子的关系

图4 不同算法对活跃节点数的影响

（2）MCA 算法与传统集群算法的比较：在以上分析的基础上，采用不同的算法对比验证MCA 算法在节约能耗上的效率。在进行网络部署时，为了保证服务质量（QoS），通常采用冗余部署，但当节点密度较大时，由于节点感知区域的重叠较多，又会造成浪费，因此需要采用节点调度的方法来使节点轮换工作，从而节约网络能耗，延长网络生命周期。

本实验以集群规模因子γ＝0.15为例来说明不采用集群算法、采用单成员集群算法和多成员集群算法时对网络性能的影响。图4显示了采用不同算法时，在不同的节点部署密度情况下，网络中的活跃节点数。图5显示采用不同算法时，网络中存活节点的数量随时间变化的趋势。

图5 不同算法对存活节点数量的影响

从图4中可以看出，在不采用集群算法时，网络中的节点在工作时全部处于活跃状态，其优点是获取的信息丰富，相对准确，缺点是采集的信息量庞大，冗余数据非常多，在采集、处理以及传输过程中都对节点产生巨大能耗压力；在采用成员集群算法时，与不采用集群算法相比，网络中的活跃节点数有明显的降低，这将很大程度的延长网络的生命周期；在采用多成员集群算法时，网络中的活跃节点数比单成员集群算法中更少，因为采用单成员集群算法时，节点只属于一个集群，不存在节点间的协作，而多成员集群算法集群与集群间具有共同节点，可以通过MCS调度方法对节点进行协调调度，进一步降低需要工作的节点数。从图4 还可以看出，在节点密度大的情况下，在多成员集群算法的效率更高，效果更好。

从图5中可以看出，在不采用集群算法时，由于网络中的所有节点在工作时会全部处于活跃状态，所以网络的生命周期等于其节点的生命周期。因为在网络工作的时间内所有节点能量的消耗是一致的，所以当所有节点的能量同时耗尽时整个网络也会随之死亡；在采用集群算法后，图中每一个下降的台阶都说明网络中的一部分节点能量耗尽，但整个网络还可以工作。在采用多成员集群算法后，整个网络直到6.5T （T 为一个节点耗尽能量时所能工作的时间长度）时所有节点才全部死亡；而采用单成员集群算法也可以达到一个较好的网络生存时长，可以达到4.5T，但是效果还是没有采用多成员集群算法好，这是因为单成员集群算法只有簇内协作，没有簇间协作。簇间协作可以进一步降低工作节点的冗余，提高网络中节点整体的利用率，降低能量消耗。

5 结束语

本文针对单成员集群算法不存在集群间相互协作，从而造成信息冗余和能量浪费的缺点，提出了多成员集群算法，根据节点与簇头的感知区域重叠率是否达到集群规模因子来判断该节点是否属于该集群，同时在集群间协作进行节点调度的过程中，根据节点是否为公共节点、节点的剩余电量和节点前一阶段的工作状态来决定是否唤醒该节点作为本轮的工作节点。仿真验证了MCA 算法的高效性。实验结果表明了在无线多媒体传感器网络的集群中采用MCA 算法，能在满足网络感知要求的前提下，有效提高网络效率，节约能量，延长网络的生命周期。

［1］Almalkawi IT，Zapata MG，Al－Karaki JN，et al.Wireless multimedia sensor networks：Current trends and future directions［J］.Sensors（Basel，Switzerland），2010，10 （7）：6662－6717.

［2］Kyildiz IF，Melodia T，Chowdhury KR.A survey on wireless multimedia sensor networks［J］.Computer Networks，2007，51 （4）：921－960.

［3］WANG Ruchuan，SUN Lijuan.Wireless multimedia sensor network technology ［M］.Beijing：The People’s Posts and Telecommunications Press，2011：9－12 （in Chinese）. ［王 汝传，孙力娟.无线多媒体传感器网络技术 ［M］.北京：人民邮电出版社，2011：9－12.］

［4］LU Juan.Primary research on wireless multimedia sensor network ［J］.Popular Science，2012，14 （4）：73－74 （in Chinese）.［卢娟.无线多媒体传感器网络研究初探 ［J］.大众科技，2012，14 （4）：73－74.］

［5］You L，Liu C，Tong S.The lifetime optimization of wireless multimedia sensor networks under uncertain energy consumption［C］／／5th International Conference on Computer Science and Education.IEEE，2010：928－932.

［6］SUN Yan，MA Huadong.The QoS guarantee problem for wireless multimedia sensor networks［J］.Journal of Electronic，2008，36 （7）：1412－1420 （in Chinese）. ［孙岩，马华东.无线多媒体传感器网络QoS保障问题 ［J］.电子学报，2008，36（7）：1412－1420.］

［7］Alaei M，Barcelo－Ordinas JM.A method for clustering and cooperation in wireless multimedia sensor networks ［J］.Sensors，2010，10 （4）：3145－3169.

［8］Akalu K，Raimond K.Design and performance analysis of energy efficient technique for wireless multimedia sensor networks using machine learning algorithm ［C］／／World Congress on Information and Communication Technologies.IEEE，2011：1127－1132.

［9］Agrakhed J，Biradar GS，Mytri VD.Cluster based energy efficient QoS routing in multi－sink wireless multimedia sensor networks［C］／／7th IEEE Conference on Industrial Electronics and Applications.IEEE，2012：731－736.

［10］Khan ZA，Auguin M.A multichannel design for QoS aware energy efficient clustering and routing in WMSN ［J］.International Journal of Sensor Networks，2013，13 （3）：145－161.

［11］GU Xiaoyan，SUN Lijuan，GUO Jian，et al.Optimization strategy of coverage quality and node dormancy in wireless sensor networks ［J］.Computer Simulation，2011，28 （9）：127－131 （in Chinese）.［顾晓燕，孙力娟，郭剑，等.无线传感器网络覆盖质量与节点休眠优化策略 ［J］.计算机仿真，2011，28 （9）：127－131.］