宋晓莹, 温涛, 孙伟, 张启龙
东北大学 软件中心，辽宁 沈阳 110819
收稿日期：2015-11-05
基金项目：国家自然科学基金资助项目 (61170169, 61170168)。
作者简介：宋晓莹 (1984-)，女，辽宁朝阳人，东北大学博士研究生;
温涛 (1962-)，男，辽宁大连人，东北大学教授，博士生导师。

摘要：针对多对一的无线传感器网络“热点”问题，提出了一种基于多准则决策方法的不等簇数据收集算法 (unequal clustering data gathering algorithm based on multiple criteria decision，UCDGAMCD).采用直觉模糊层次分析法和层次模糊积分的多准则决策方法来竞选簇首，提出了一个新的簇首竞争半径，使其能够适应节点能量异构及节点非均匀分布的网络环境.根据邻居簇首的剩余能量和传输能耗，提出了簇首间按比例分配传输数据的路由方式，使其能量消耗更加均衡.仿真结果表明UCDGAMCD在节点均匀和非均匀分布的两种实验场景中都获得了较长的网络寿命.
关键词：无线传感器网络分簇算法直觉模糊层次分析法多准则决策方法网络寿命
Unequal Clustering Data Gathering Algorithm Based on Multiple Criteria Decision Making for WSNs
SONG Xiao-ying, WEN Tao, SUN Wei, ZHANG Qi-long
Software Center, Northeastern University, Shenyang 110819, China
Corresponding author: SONG Xiao-ying, E-mail: songxiaoying@neusoft.edu.cn
Abstract: Focusing on the hot spot problem in many to one wireless sensor networks, an unequal clustering data gathering algorithm based on multiple criteria decision (UCDGAMCD) was proposed. The intuitionistic fuzzy analytic hierarchy process and multiple criteria decision making of hierarchical fuzzy integral were used to select cluster heads (CHs), and a new cluster head competition radius was proposed to make it fit for the network scenarios with energy heterogeneous and nodes non-uniform distribution. To balance energy consumption, a routing algorithm with data ratio distribution was proposed based on residual energy of CHs and transmission energy consumption. The simulation results demonstrated that UCDGAMCD can obtain higher network lifetime in two scenarios—node uniform and non-uniform deployment.
Key Words: wireless sensor networksclustering algorithmintuitionistic fuzzy analytic hierarchy processmultiple criteria decision makingnetwork lifetime
目前，随着无线传感器节点的集成化和微型化，节点的电源大多采用能量受限的电池^[1].由于节点通常位于无人区域或危险环境中，难以进行能源补给，而可再生能源技术目前尚不成熟.因此，通过优化系统能耗，最大限度地延长网络寿命成为无线传感器网络面临的首要挑战^[2].
近年来，分簇的数据收集算法是降低能耗延长网络寿命的有效方法之一^[3].目前，已有大量的文献研究了不等簇分簇算法.从采用的方法划分：一类是基于精确数学的不等簇分簇数据收集算法；另一类是基于模糊数学的不等簇分簇数据收集算法.无论是哪种算法，它们大多适用于节点均匀分布和初始能量同构的网络场景.鲜有同时考虑节点随机非均匀分布和能量异构的更贴近现实的网络场景.
在基于精确数学的不等簇分簇数据收集算法中，DCPVP^[4]是一种基于投票和优先级思想的不等簇分簇数据收集算法.在DCPVP中，簇规模由节点到基站的距离和局部节点的密度决定.而簇首的选择基于邻居节点间的平均距离、剩余能量和被选择的时间.实验表明，DCPVP不仅延长了网络寿命而且大大降低了网络的消息复杂度.然而，该数据收集算法仅适用于节点同构和均匀分布的网络场景.虽然，IDUC^[3]同时考虑的节点有非均匀分布和能量异构的情况，但是，在竞争簇首的过程中，仅考虑了候选簇首的剩余能量，簇首选择因素考虑得不够全面.
在基于模糊数学的不等簇分簇数据收集算法中，文献[5]提出了一种基于多准则决策方法的分簇算法FAHP.然而，该分簇算法运用梯形模糊层次分析法确定准则重要性程度时，存在一定的局限性.因为模糊层次分析法中的模糊集能在一定程度上表示决策者对研究对象的主观判断，但不能精确表达弃权或犹豫不决的情况^[6].直觉模糊层次分析法是模糊层次分析法的扩充和发展，在处理上述不确定性方面更具灵活性和实用性.
综上所述，本文提出了一种基于多准则决策方法的分布式不等簇分簇数据收集算法UCDGAMCD.首先，采用直觉模糊层次分析法和层次模糊积分的多准则决策方法来竞选簇首.UCDGAMCD在簇首竞争的过程中，综合考虑多种因素之间的关联关系，避免了使用OWA算子时的假设条件，即每个属性都是相互价值独立的.其次，提出了一个新的簇首竞争半径，使其能够适应节点能量异构及节点非均匀分布的网络环境.然后，根据邻居簇首的剩余能量和传输能耗，提出了按比例分配传输数据的路由方式，使其能量消耗更加均衡.最后，仿真结果表明UCDGAMCD在两种实验场景中都获得了较长的网络寿命.
1 UCDGAMCD算法UCDGAMCD算法的整个操作被划分为以轮^[7]为时间单位，每一轮分为簇拓扑建立阶段和数据传输阶段.
1.1 簇首选择在获得节点成为簇首的综合得分过程中，首先，需建立综合评价簇首选择层次结构.然后，分别求得层次模糊积分模型所需的属性评估值 (h) 和属性重要性程度 (g).
为了提高能量有效性同时考虑到服务质量可靠性的要求，将簇首选择的主准则分为能量状况、服务质量状况及节点位置状况.除此之外，根据影响簇首选择的多个因素，可建立层次结构.
1.1.1 簇首综合评价的属性评估值 (h)在初始化阶段完成后，每个节点都计算出邻节点的最大和最小剩余能量、邻节点数目及网络中节点与基站的最大最小距离等信息.通过网络初始化过程，每个节点可以获得计算评估值所需要的参数值.然后，开始计算这些属性的评估值 (h).
1)?剩余能量 (E):在无法自由替换电池节点构成的无线传感器网络中，能量是最重要和稀缺的资源.第i个节点剩余能量评估值定义为

(1)

式中：E_max和E_min分别是节点i的邻居节点中最大和最小的剩余能量；E_r是节点i的剩余能量.
2)?消息代价 (M)：消息代价是在簇拓扑建立过程中，由节点获得接收和发送消息的数目来确定.消息代价直接影响节点能量的消耗，所以，消息代价的评估值定义为

(2)

式中：M_C为节点i接收和发送消息的总数目；M_T为其所有邻居节点接收和发送消息的总数目.M_C值越大，消息代价M_i越低.
3)?覆盖因子 (CI)：覆盖保持是保证服务质量 (QoS) 最基本的问题之一.选择覆盖保持较好的节点作为簇首能够有效延长网络的功能时间^[8]，并节省节点的剩余能量.因此，覆盖因子是判断一个节点服务质量的主要因素，其评估值定义为

(3)

式中：|C(i)|表示节点i覆盖邻居节点个数；|O(i)|表示节点i被其他节点覆盖的邻居节点个数；|∪_i=1ⁿC(i)|表示覆盖节点i邻居节点的总节点数.CI_i的值越高，节点i单独覆盖的节点数越多，该节点的覆盖保持性越好.
4)?链接可靠性 (R)：在数据传输的过程中，任意节点失效或是包丢失都会导致大量的包丢失.因此，服务质量考虑可靠的数据递交是十分必要的.簇首节点主要负责接收成员节点和其他簇首的数据，所以，可靠性高的节点作为簇首的概率应该更大.节点可靠性的评估值定义为

(4)

式中：B_ava(i) 为节点i可用的缓冲区空间；B_total(i) 为节点i缓存区的总空间.节点的缓存区可用空间越大，节点i的可靠性越高.
5)?邻居节点数 (N):在文献[7]中，通过网络中节点的初始信息，可以求得在网络能量消耗最小时的最优簇个数，从而进一步获得最优的簇成员个数.当一个节点的邻居节点数量越接近最佳邻居节点数时，该节点成为簇首的概率就越大.邻居节点数评估值定义为

(5)

式中：N_i为节点i的邻居节点数目；N_o为最佳簇成员数目.
6) 与基站距离 (D):节点与基站的距离也是成为簇首需要考虑的关键因素，因为距离与能耗具有直接的关系.节点与簇首的距离越大，成为簇首的概率相对越小.因此，与基站距离的评估值定义为

(6)

式中：d_max为网络中的节点与基站的最大距离；d_min为网络中的节点与基站的最小距离；d_{(i, Sink)}为节点i与基站的距离.当节点i与基站的距离越大，D_i值越小.
1.1.2 确定簇首综合评价的属性重要性程度首先，请多位专家通过对准则层和子准则各指标对上一目标层的重要性进行两两比较.综合各位专家的意见，建立直觉模糊互补判断矩阵.其中，第二层所有属性对目标层的直觉模糊互补判断矩阵为

(7)

第三层子准则层各属性对第二层准则层属性的直觉模糊互补判断矩阵为

(8)

(9)

(10)

根据文献[9]中的算法1，用Matlab R2013(b) 实现了该算法，并对4个模糊互补判断矩阵进行一致性检验，其中，λ=0.4，d=0.1.经过对这些矩阵进行一致性检验及调整，得到上述4个矩阵的满意一致性矩阵：

(11)

(12)

(13)

(14)

最后，计算权重.获得满意一致性矩阵后，根据文献[9]中的公式 (1) 即可求得第二层中所有属性对目标层的权重W = (0.375, 0.315 8, 0.319 8).同理可得第三层子准则层各属性相对于上一层的各权重及子准则层各属性相对于目标层元素的最终组合权重，如表 1所示.
表 1(Table 1)

表 1 基于直觉模糊层次分析的权重Table 1 Weights based on intuitionistic fuzzy analytic hierarchy process 属性 L21 0.375 L22 0.315 8 L23 0.319 8 对目标层的权重值 L31 0.264 3 0.338 0 0.302 9 0.302 7 L32 0.224 2 0.000 0 0.000 0 0.084 1 L33 0.261 3 0.345 4 0.000 0 0.207 1 L34 0.000 0 0.307 8 0.000 0 0.097 2 L35 0.000 0 0.000 0 0.341 6 0.109 2 L36 0.247 0 0.000 0 0.344 4 0.202 8

表 1 基于直觉模糊层次分析的权重 Table 1 Weights based on intuitionistic fuzzy analytic hierarchy process

1.2 簇拓扑的建立1.2.1 综合评价值与簇首广播时间的映射簇首广播采用与文献[5]相同的计时广播机制.根据节点成为簇首的综合评价得分映射到触发竞选簇首消息的时间轴上.其目的是使综合评价得分高的节点较快地以簇首竞争半径R_iC广播竞选簇首的消息HEAD_MASSAGE.发布竞争簇首消息的时间：

(15)

式中：δ为0.9到1的随机数，为了避免消息碰撞；CS_i为通过层次模糊积分计算的节点成为簇首的综合评价得分；T_C为预先设置的成簇时间.
1.2.2 簇首竞争半径在异构的网络环境中，节点具有异构的初始能量.当网络中的节点消耗相同的能量时，具有较低初始能量的节点将过早死亡，从而降低了网络寿命.为了完全体现高能量节点的优势，让其承担更多的任务，在建立不等簇拓扑时，不仅考虑节点与基站的距离，还要考虑节点具有的能量高低.然而，当这些节点与基站的距离相似，而且剩余能量也接近时，除了这两个因素以外，还需要考虑节点非均匀分布的因素.因此，提出了一个新的竞争簇首半径，如式 (16) 所示.使其能够在节点能量异构且呈非均匀分布的网络场景中，高效地构建不等簇拓扑，从而避免能量消耗不均衡的现象.

(16)

式中：d_max和d_min为网络中节点距离基站的最大和最小距离；d_{(i, Sink)}为节点i与基站的距离；E_max为节点i的邻居节点中最大的剩余能量；E_ir为节点的当前剩余能量；n_i为节点i的邻居节点数；N为网络中的节点总数；R₀为初始簇首竞争半径.
1.3 数据传输在簇间传输阶段，提出一种按比例分配的路由传输方式使簇间数据传输的能量消耗更加均衡.如果簇首与基站的距离没有超过门限值，则采用直传的方式直接将数据传送到基站.如果超过了门限值，则采用提出的按比例分配的路由方式传输数据.具体过程如下：首先，每个簇首CH_i(i=1, 2, …, K) 以2R_iC广播半径广播一条CH_RELAY_MESSAGE消息，其目的是能够覆盖到其他簇首.这条消息主要包括簇首ID、当前剩余能量及该簇首与基站的距离.接收到消息后，如果邻居簇首到基站的距离小于簇首CH_i与基站的距离，则簇首CH_i计算和这些邻居簇首CH_j(j=1, 2，…，L, L为CH_i邻居簇首个数) 的距离，并建立一个邻居簇首信息表.
簇首CH_i运用式 (17) 计算代价函数 (DRC)，将数据包按比例传输到其邻居簇首CH_j上.

(17)

式中：E_{t(i, j)}为从CH_i到簇首CH_j传输数据的能耗；E_jr为邻居簇首CH_j当前剩余能量.
假设CH_i的数据量为M_i，则需要按比例分配公式，如 (18) 所示，向邻居簇首传输数据量.也就是说向邻居簇首1传输的数据量为M_i×DRC (I, 1)，向邻居簇首2传输的数据量为M_i×DRC (I, 2)，依次类推.

(18)

2 仿真实验仿真实验的运行环境为Intel Pentium双核 (2.2 GHz) 处理器，2 GB内存，采用Matlab R2013(b) 实验平台.与EEUC，IDUC，FAHP在两种网络场景内进行仿真实验与对比，仿真环境参数如表 2所示.
表 2(Table 2)

表 2 仿真参数Table 2 Simulation parameters 参数 值 基站坐标 (250, 100) 节点初始能量/J 1~3 数据包大小/b 4 000 通信半径/m 25 Eelec/(nj·b-1) 50 εfs/(pJ·b-1·m-2) 10 ESEN/(J·b-1) 0.5 ECOM/(nJ·b-1) 5 d0/m 80

表 2 仿真参数 Table 2 Simulation parameters

实验的两个场景描述如下：
Ⅰ.100个节点均匀分布在200 m×200 m的区域内.
Ⅱ.100个节点非均匀分布在200 m×200 m的区域内.
在两个实验场景内分别比较四个算法的网络寿命.设置UCDGAMCD中的关键参数:R₀=140 m，α =0.3，β=0.3，γ=0.4.而IDUC也是关于异构传感器网络不等分簇，它的关键参数:α= 0.3，β= 0.3，γ = 0.4，ω = 0.5，R₀=140 m.图 1为四种算法的网络寿命在场景Ⅰ中的比较.从图 1中可以观察出UCDGAMCD和IDUC算法的网络寿命比EEUC和FAHP的要长.这主要是因为UCDGAMCD和IDUC两种算法在簇拓扑构建的过程中，考虑了邻居节点的数量，从而使分簇更加合理.而UCDGAMCD的网络寿命比IDUC长些，这主要是因为UCDGAMCD不仅采用多准则决策综合评价作出簇首选择，而且簇间数据传输还采用按比例传输的路由方式，使能量消耗更加均匀.虽然，FAHP在簇拓扑构建的过程中，没有采用不等簇的分簇方式，但是在场景Ⅰ中，其网络寿命与不等簇的IDUC十分接近.这主要是因为FAHP在竞选簇首的过程中也采用了综合评价节点来竞选簇首.
图 1(Fig. 1)

图 1 四种算法的网络寿命在场景Ⅰ中的比较Fig.1 Comparison of network lifetime of four algorithms in scenario Ⅰ

图 2为四种算法的网络寿命在场景Ⅱ中的比较.在图 2可以观察到四种算法在出现第一个死亡节点之后，随着仿真时间的持续增长，其存活节点个数都是呈线性下降的，并没有造成网络分裂.另外，从图 2中还可以观察到UCDGAMCD的网络寿命明显长于其他三种算法.这主要是因为在簇首竞争的过程中，采用层次模糊积分和模糊层次分析的多准则决策来综合评价节点作为簇首；而且UCDGAMCD算法还考虑了节点非均匀分布对簇首竞争半径的影响，从而构建了更加合理的不等分簇拓扑；同时，簇间数据传输采用按比例分配的路由方式，进一步均衡了网络的能量消耗.因此，UCDGAMCD的网络寿命明显比其他三种算法长.
图 2(Fig. 2)

图 2 四种算法的网络寿命在场景Ⅱ中的比较Fig.2 Comparison of network lifetime of four algorithms in scenario Ⅱ

3 结论本文提出了一种基于多准则决策方法的不等簇数据收集算法UCDGAMCD.首先，采用直觉模糊层次分析法和层次模糊积分的多准则决策方法来竞选簇首.其次，根据簇首与基站的距离、剩余能量和邻居节点个数，提出了一个新的簇首竞争半径，使其能够构建更加合理的不等簇拓扑.然后，为了均衡簇首间能耗，提出了按比例分配传输数据的路由方式.最后，仿真结果表明UCDGAMCD在两种实验场景中都获得了较长的网络寿命.
虽然，UCDGAMCD大大降低了网络能耗，但是不能适应数据包重发与丢失的情况.下一步工作将针对该问题展开讨论.
参考文献

[1]	Afsar M M, Tayarani N M H. Clustering in sensor networks:a literature survey[J].Journal of Network and Computer Applications, 2014, 46: 198–226.DOI:10.1016/j.jnca.2014.09.005
[2]	Zhang D, Wang X, Song X, et al. A new clustering routing method based on PECE for WSN[J].EURASIP Journal on Wireless Communications and Networking, 2015, 2015(1): 1–13.
[3]	Chen C, Gu X, Yu J, et al. IDUC:an improved distributed unequal clustering protocol for wireless sensor networks[J].International Journal of Distributed Sensor Networks, 2015(4): 682–693.
[4]	Hematkhah H, Kavian Y S. DCPVP:distributed clustering protocol using voting and priority for wireless sensor networks[J].Sensors, 2015, 15(3): 5763–5782.DOI:10.3390/s150305763
[5]	Gao T, Jin R C, Song J Y, et al. Energy-efficient cluster head selection scheme based on multiple criteria decision making for wireless sensor networks[J].Wireless Personal Communications, 2012, 63(4): 871–894.DOI:10.1007/s11277-010-0172-8
[6]	Atanassov K T. Intuitionistic fuzzy sets[J].Fuzzy Sets and Systems, 1986, 20(1): 87–96.DOI:10.1016/S0165-0114(86)80034-3
[7]	Heinzelman W B, Chandrakasan A P, Balakrishnan H. An application-specific protocol architecture for wireless microsensor networks[J].IEEE Transactions on Wireless Communications, 2002, 1(4): 660–670.DOI:10.1109/TWC.2002.804190
[8]	Gu X, Yu J, Yu D, et al. ECDC:an energy and coverage-aware distributed clustering protocol for wireless sensor networks[J].Computers & Electrical Engineering, 2014, 40(2): 384–398.
[9]	Zhang C, Li W, Wang L.AHP under the intuitionistic fuzzy environment.[C]//Proceedings of 8th International Conference on Fuzzy Systems and Knowledge Discovery.Shanghai, 2011:583-587.