新的位置感知分簇算法

田炜，杨震

(1. 南京邮电大学 通信与信息工程学院，江苏 南京 210003；2. 南京邮电大学 信号与信息处理研究院，江苏 南京 210003)

1 引言

在资源受限无线传感器网络（WSN）中，由于网络节点随机部署、电池供能、不具备持续能量供应等原因，能量有效性是其首要解决的问题[1,2]。而且WSN是应用相关性非常强的网络，只有保证数据传输到指定节点（如信宿）或区域，才能确保数据的可用性，即网络的可靠性。因此在提高 WSN网络能量有效性的同时，也要确保网络的可靠性。

分簇网络结构由于具有良好的网络扩展性，便于能量管理、负载平衡、资源分配等特点，成为目前国内外解决WSN能量有效性的主要方法之一。WSN分簇算法的典型代表 LEACH(low-energy adaptive clustering hierarchy)算法[3]，其选取簇头的过程为：节点产生[0,1]之间的随机数，若其小于阈值nT，则当选为簇头。nT的计算如式(1)所示。

其中，P是簇头数与总节点数的百分比；r是当前选举轮数；G是当前轮非簇头节点集。

作为经典算法，LEACH算法成为研究WSN分簇算法的主要参考。但由于 LEACH算法簇头选取的随机性，导致能量及负载不平衡。因此研究者们提出了许多新的分簇算法。如文献[4]通过监测邻居节点信号功率，实时估计活动节点数并计算当选簇头的概率，提出动态分簇方法。RDCA[5]通过收集邻居节点信息，根据网络局部拓扑信息进行分簇。MWBC[6]先通过节点间的信息交互，获得局部网络信息(如节点度、当前能量值、发射功率、链路质量、相对位置等)，然后根据应用背景进行分簇决策，并预设簇的最大规模。EDCA[7]根据用户要求的误差门限及节点数据的空间相关性马尔可夫模型，将事件感知区域划分成虚拟极坐标等价层，在等价层中选取剩余能量最大的节点作为簇头。

但已有的分簇算法存在以下问题：1）利用网络局部信息（如节点度、信号功率等）选取簇头，节点就必须收集等待邻居节点信息，势必增大网络延时，增加网络控制传输开销，从而降低算法的整体性能；2）采用预测模型选取簇头，在没有先验知识的前提下，往往很难得到理想的预测结果，难以适应WSN拓扑快速变化的特点，使得算法实现困难，增加算法的复杂性；3）算法没有考虑网络的可靠性，减弱了算法的适用性。

基于位置的分簇算法因其无需建立、维护和存储路由表，无需网络拓扑信息，算法实现简单，控制开销小等特点，而在WSN中得到广泛的关注和研究。如GAF算法[8]根据节点位置信息将监测区域划分为虚拟正方形单元格，在每个单元格中定期选举出一个簇头节点。然而理论分析与仿真比较表明，蜂窝结构更能有效地提高能量有效性，延长网络寿命[9]。

因此本文在蜂窝结构的基础上，引入角度比和距离比2个参数，提出位置感知分簇算法(LACA，location aware clustering algorithm)。该算法不仅有效地提高了网络能量有效性，保证网络可靠性，而且算法实现简单，控制传输开销小。

本文第2节给出LACA的算法思想、算法分析和算法设计；第 3节给出网络模型；第 4节通过NS2仿真验证，分析比较LEACH、GAF和LACA在能量有效性、网络寿命、可靠性和分簇结构上的性能；第5节是结束语。

2 LACA

2.1 算法思想

如图1所示，假设以通信距离R为半径的圆形区域是最大分簇规模，则以簇头节点为中心，通信距离R为边长的正六边形结构，将是最为理想的分簇结构。然而在实际中，由于WSN部署的随机性，无法保证簇头节点正好处于正六边形中心。因此，难以形成理想的正六边形分簇结构。

图1 LACA算法思想

但是假设节点已知其位置信息[10～13]，则可以计算出节点（如节点13和20）之间的距离及其连线与水平线之间的夹角。通过角度比和距离比，就可以确定节点偏离理想簇头位置（如节点10）的程度。因此，只要设置合理的角度比和距离比阈值，节点就可以根据角度比和距离比自主地决定是否作为簇头，从而形成较为理想的分簇结构。为此，本文将WSN节点分为簇头节点（如节点13，负责收集簇成员数据并转发簇间数据）、簇成员节点（如节点30，负责监测收集簇内数据并将簇内数据发送到其簇头）和分簇网关节点（相邻分簇相交区域内的节点，如节点20，负责簇间数据以及簇头形成信息的转发），并定义

角度α

距离比

其中，Nx和 Ny表示节点N的横纵坐标，Mx和 My表示节点M的横纵坐标，R表示通信距离。

角度比η表示节点（如节点13）在角度上接近理想簇头（如节点10）的程度。

距离比δ表示节点（如节点13）在距离上接近理想簇头（如节点10）的程度。

LACA算法思想就是根据节点的位置信息，通过η和δ感知参数，在角度和距离上选取逼进理想簇头的节点作为簇头，从而形成较为理想的分簇结构，以此提高WSN的能量有效性，并通过η和δ阈值的合理设置，确保网络的可靠性。

同时，为了避免过度消耗某节点的能量，有效地均衡网络能量和负载，定义

偏离角度

并将式（2）修改为式（6）。角度α

引入偏离角度Δ，意味着新一轮的簇头位于前一轮簇头选取范围旋转Δ后的区域内，从而实现动态轮换簇头节点，有效地均衡网络能量及负载。

2.2 算法分析

WSN的可靠性就是保证网络数据的可用性。即网络节点数据互达或确保数据发送到指定节点（或区域）。在本文中，采用孤立节点（与其他节点互不可达的节点）数来验证网络的可靠性。当孤立节点数为0时，表示网络可靠性得到保证。η和δ的阈值就是根据孤立节点数为0时设置的。η越小，意味着节点在角度上更逼进理想簇头，δ越大，意味着节点在距离上更逼进理想簇头。为此，在NS2[14]仿真环境中（仿真参数如表 1所示），针对100个节点的网络场景，具体分析η和δ阈值情况，其他网络规模类似。

从图2可知，当η≥0.1时，孤立节点数为0。图3是η=0.1时得到的δ值，从图3中可知，当δ≥0.6，孤立节点数为0。δ越大，意味着接收节点距离发送节点越远，将会由于信道衰落等原因引起误码，导致节点无法正确接收数据。因此，结合仿真结果，针对100个节点的WSN，η和δ分别设置为0.1和0.8。

表1 NS2仿真参数

图2 角度比阈值分析

图3 角度比确定距离比阈值分析

2.3 算法设计

2.3.1 簇头告知信息分组结构

节点当选为簇头后，需要向其他节点发送告知信息，以便其他节点决定是否成为该簇头的成员。簇头告知信息分组结构如图4所示。其中，NdType=0表示簇头节点，NdType=1表示簇成员节点，NdType=2表示分簇网关节点；clsNum表示轮数，第一轮分簇设为0，以后每一轮分簇，由信宿自动加1。

图4 簇头告知信息分组结构图

图5 LACA工作过程

2.3.2 工作过程

LACA的工作过程以“轮”进行，每轮分为建立阶段和稳定阶段2个阶段，其工作过程如图5所示。

在建立阶段，信宿首先发送簇头告知信息，将NdType设置为0，X和Y设置为其横纵坐标，发起新一轮的分簇过程。节点接收到簇头告知信息后，按式(3)和式(4)计算η和δ。若η小于阈值，δ大于阈值，则当选为分簇网关节点，将NdType设置为2，X和Y设置为其横纵坐标，并根据δ的大小，加入最小的δ分簇，同时转发簇头告知信息；否则，当选为分簇成员节点，设置 NdType为1，并根据δ的大小，加入最小的δ分簇，同时丢弃接收到的信息分组。若节点接收到分簇网关节点转发的簇头告知信息，按式(3)和式(4)计算η和δ。若η小于阈值，δ大于阈值，则当选为分簇簇头节点，将NdType设置为0，X和Y设置为其横纵坐标，发送簇头告知信息；否则丢弃接收到的信息分组。从而自动完成分簇过程，进入稳定阶段。

在稳定阶段，分簇网关和簇成员节点持续监测数据，并将数据发送到簇头后转发给信宿。持续一段时间后，进入下一轮工作周期，由信宿开始新一轮的分簇过程，并将clsNum加1。

3 网络模型

WSN模型假设如下。

1) 节点同构，静态随机分布在二维平面上，并且节点自身位置已知；

2) 节点使用全向天线，通信距离为R(m)；

3) 最大分簇规模是以节点通信距离 R为半径的圆形区域；

4) 分簇的发起节点为信宿。

4 仿真与性能分析

为了验证LACA的有效性，在NS2仿真环境中，对100个节点的网络分析比较LEACH，GAF和LACA算法在能量有效性、网络寿命、可靠性和分簇结构上的性能。仿真参数如表1所示。正方形边长为R / 5，正六边形边长为R。

并定义能量有效性γ，如式(7)所示。

其中，E总表示算法在综合情况下（如网络冲突，信道竞争，控制开销等）消耗的总能量， ELEACH表示LEACH算法消耗的总能量。显然γ越小，算法的能量有效性越高。

4.1 能量有效性

从图6可知，在能量有效性上，与LEACH算法相比，GAF算法提高了约27%，LACA提高了约30%。在网络运行前期阶段（200s之前），GAF算法的能量有效性优于LACA，随着网络运行时间的推移，LACA的能量有效性优于GAF算法。这是因为 GAF的簇成员节点采用睡眠方式，并在单元格中周期性地选取簇头，而LACA则是节点根据其位置信息自主地决定是否作为簇头。

图6 能量有效性随时间的变化

4.2 网络寿命

网络寿命是指网络中出现第一个死亡节点（即耗尽能量的节点）的网络生存时间。

从图 7可知，在网络寿命上，GAF算法约为LEACH算法的2倍，LACA比GAF算法延长了约10%。LACA出现死亡节点的时间和全部节点死亡的时间都很晚，而且2个时间差较短，表明LACA延长了网络寿命，有效地均衡了网络能量和负载。

图7 存活节点数随时间的变化

4.3 可靠性

可靠性是保证网络数据的可用性。当孤立节点数为0时，表示网络可靠性得到保证。从图8可知，LEACH算法和GAF算法出现随机性的孤立节点数，表明其网络可靠性得不到任何保证。LACA有效地抑制了孤立节点的产生，确保了网络的可靠性。这是因为LEACH算法和GAF算法没有考虑网络的可靠性，而LACA则在保证可靠性的前提下选取簇头，其孤立节点数远远小于LEACH算法和GAF算法。

图8 孤立节点数随时间的变化

4.4 分簇结构

图9 ～图11分别表示LEACH算法、GAF算法和LACA在第三轮分簇时形成的分簇结构，其中实心黑点表示簇头节点。从图中可知，LEACH算法和GAF算法都存在孤立节点（图9、图10中画圆圈的节点）。这些孤立节点不属于任何分簇，既接收不到簇头的数据，又不能将其数据汇集到簇头，因此降低了网络的可靠性。而LACA则有效地保证了网络的可靠性。

图9 LEACH算法的分簇结构

图10 GAF算法的分簇结构

图11 LACA的分簇结构

5 结束语

针对资源受限 WSN能量有效性和可靠性问题，本文在研究分簇算法的基础上，提出一种新的位置感知分簇算法（LACA）。算法采用位置感知策略选取簇头，并依据网络可靠性合理设置感知参数阈值。LACA不仅能量有效性高、网络寿命长、网络能量和负载均衡性好，而且有效地抑制了孤立节点的产生，保证了网络可靠性。如何使算法根据网络规模自适应地改变角度比和距离比阈值，是需要进一步研究的内容。如何将睡眠唤醒机制引入LACA中，从而设计出更加高效的分簇算法，是下一步进行研究的内容。

[1] AKYILDIZ I F, SU W, SANKARASUBRAMANIAM Y, et al. A survey on sensor network[J]. IEEE Communication Magazine,2002,8∶102-114.

[2] 孙利民, 李建中, 陈渝等. 无线传感器网络[M]. 北京∶ 清华大学出版社, 2005.SUN L M, LI J Z, CHEN Y, et al. Wireless Sensor Network[M]. Beijing∶ Qinghua University Press, 2005.

[3] HEINZELMAN W B,CHANDRAKASAN A P,BALAKRISHNAN H.An application-specific protocol architecture for wireless microsensor networks[J]. IEEE Transactions on Wireless Communications,2002,l(4)∶ 660-670.

[4] MING Y, LEUNG K K, MALVANKAR A. A dnamic clustering and energy efficient routing technique for sensor networks[J].IEEE Trans on Wireless Communications, 2007, 6(8)∶3069-3079.

[5] 胡静,沈连丰,宋铁成等.新的无线传感器网络分簇算法[J].通信学报,2008, 29(7)∶20-26.HU J, SHEN L F, SONG T C, et al. Novel clustering algorithm for wireless sensor networks[J]. Journal on Communications,2008, 29(7)∶ 20-26.

[6] 黄河清,姚道远,沈杰等.一种基于多权值优化的无线传感网分簇算法的研究[J].电子与信息学报,2008,30(6)∶1489-1492.HUANG H Q, YAO D Y, SHEN J, et al. A multi-weight based clustering algorithm for wireless sensor networks[J]. Journal of Electronics &Information Technology, 2008,30(6)∶1489-1492.

[7] 王天荆, 杨震, 胡海峰. 基于空间相关性的事件驱动无线传感器网络分簇算法[J]. 电子与信息学报,2008,30(3)∶699-702.WANG T J, YANG Z, HU H F. An event driven clustering algorithm based on spatial correlation in wireless sensor networks[J]. Journal of Electronics & Information Technology, 2008,30(3)∶699-702.

[8] XU Y, HEIDEMANN J, ESTRIN D. Geography-informed energy conservation for ad hoc routing[A]. Proc of 7th Annual Int’l Conf on Mobile Computing and Networking[C]. Rome , Italy ACM Press,2001.70 - 84.

[9] WANG Z, ZHANG J. Energy efficiency of two virtual infrastructures for MANETs[A]. Performance, Computing and Communications Conference , 2005 , IPCCC 2005, 24thIEEE International[C]. Phoenix,Arizona, USA∶ IEEE Press, 2005. 547 - 552.

[10] HOFMANN WELLENHOF B, LICHTENEGGER H, COLLINS J.Global Positioning System∶ Theory and Practice[M]. Springer Verlag,1997.

[11] BULUSU N, HEIDEMANN J, ESTRIN D. GPS-less low cost outdoor localization for very small devices[J]. IEEE Personal Communications Magazine, 2000, 7(5)∶ 28-34.

[12] CARUS A, URPI A, CHESSA S, DE S.GPS-free coordinate assignment and routing in wireless sensor networks[A]. Proc 24th Annu Joint Conf. IEEE Comput Commun Soc (INFOCOM ’05)[C]. 2005,1∶150-160.

[13] WARD A, JONES A, HOPPER A. A new location technique for the active office[J]. IEEE Personal Communications, 1997,4(5)∶ 42-47.

[14] The network simulator-ns-2[EB/OL]. http∶//www.isi.edu/ nsnam/ns/index.html.2008.