基于多目标优化的无线传感网无干扰分簇算法

An Interference-Free Clustering Algorithm for Wireless Sensor Networks Based on Multi-Objective Optimization

摘要

为减少无线传感网的网络能耗并延长网络寿命，提出了一种基于多目标优化的无线传感网无干扰分簇算法（interference-free clustering algorithm，IFCA）。该算法在保证簇间无通信干扰的前提下，将网络能耗和网络覆盖作为优化目标，使用遗传算法和非支配排序优化分簇方案。通过仿真实验分析了节点数量、监测点数量、节点通信半径和节点覆盖半径对本文算法划分网络分簇的结果及无干扰分簇后网络覆盖的影响。仿真结果表明，本文算法适合于具有大量节点的大型无线传感网，在这种网络中，本文算法会智能设置传感器节点的角色，即成员节点、簇头节点和孤立节点，从而达到了对监测点的最优覆盖，实现了网络节能。

Abstract

In order to reduce the energy consumption of wireless sensor networks and extend the network life, an interference-free clustering algorithm (IFCA) based on multi-objective optimization is proposed. Under the premise of no communication interference between clusters, the algorithm takes the network energy consumption and network coverage as optimization objectives and uses the genetic algorithm and non-dominated sorting to optimize clustering scheme. The influence of the number of nodes, the number of monitoring points, the communication radius of nodes and the coverage radius of nodes on the clustering results of this algorithm and the network coverage after non-interference clustering are analyzed through simulation experiments. The simulation results show that the proposed algorithm is suitable for large wireless sensor networks with a large number of nodes. In this network, the algorithm intelligently sets the roles of sensor nodes, namely member nodes, cluster head nodes and isolated nodes, so as to achieve the optimal coverage of monitoring points and network energy saving.

Graphical abstract

关键词

无线传感网 / 多目标优化 / 无干扰分簇协议

Key words

wireless sensor networks / multi-objective optimization / interference-free clustering

0　 引 言

目前，无线传感网面临的一个巨大问题是网络能耗，在大型无线传感网中，因网络更加复杂且负载更大，所以其能耗问题更加严重。在这些被消耗的能量中，有相当一部分是被浪费的，能量浪费主要是和通信相关：如无线通信造成的碰撞、媒介接入中的空闲侦听等^[1]。因此，避免无线通信浪费是网络节能的一个重要研究方向。

2012年，Mamun^[2]提出一种基于帧时隙的媒介接入机制，可实现无干扰通信，适合大型无线传感网的构建。前期的研究表明，基于簇结构的网络拓扑因其节能性也非常适合于大型无线传感网^[3]。在无线网络中，TDMA（time division multiple access）是一种典型的基于帧时隙的媒介接入机制。在这种机制中，每个节点在分配给其的时隙中醒来，进行数据传输，而在其他时隙保持休眠状态。一方面，这种休眠机制确保了能耗的最小化；另一方面，因为每个时隙只分配给一个节点，所以不会造成通信干扰^[4]。在基于簇的网络中，网络节点被划分为不同的簇，每个簇都包括一个簇头节点和若干个成员节点。每个成员节点采集数据并将数据发送给簇头节点，簇头将收到的数据进行整合并发送给汇聚节点（sink）。基于簇的网络不仅节能，而且能够满足大型无线传感网的可扩展性要求^[5]。在该类网络中，时隙分配通常以簇为单位进行，即每个簇的簇头给其成员进行时隙分配。这种时隙分配相对简单，但其缺点是每个簇只负责自身的分配，而没有考虑到其他簇的分配，所以虽然簇内的通信没有干扰，但不能避免簇间通信干扰。

目前研究者已经提出了一些无线传感网分簇算法，这些算法通过对簇头选择^[6,7]、路由优化^[8]、数据融合^[9]等方面进行改进，以减少网络能耗，却很少提出涉及无干扰通信的分簇算法。但是研究人员已经认识到了无干扰分簇的重要性，如在文献[10,11]中，作者提出通过簇内时隙分配机制来避免因干扰而造成的能量浪费。然而，这些工作主要考虑了簇内的通信干扰，而没有同时考虑簇间的通信干扰。同时考虑两者的通信干扰将使模型的建立变得异常复杂，例如，在文献[12]中，将时隙分配问题建模为任务调度模型，其复杂度和节点数目成指数关系，无法用于大型无线传感网的建模。

为解决上述问题，本文提出了一种基于多目标优化的无线传感网无干扰分簇算法（interference-free clustering algorithm，IFCA）。该算法将无线传感网划分为互不干扰的簇，每个簇在进行时隙分配时，只需要关注自身簇内的时隙分配问题即可。在分簇过程中，将网络能耗和覆盖作为优化指标，使用遗传算法和非支配排序优化分簇方案，再通过简单的时隙分配，使得簇内和簇间同时实现无干扰通信，从而避免了能量浪费，延长了网络寿命。

1　 相关工作

因分簇算法具有节能和可扩展性等优点，特别适合将其应用于大型无线传感网的构建中。目前对无线传感网分簇算法^[13]的研究主要包括以下几方面。

1） 聚类算法：将无线传感网划分成不同的簇。早期的无线传感网聚类算法主要通过随机的方式生成簇，如LEACH算法^[14]等。这种随机方式的优点是简单，但显然产生的簇不一定是最优的。为了优化生成的簇，通常将一些优化算法集成在无线传感网的聚类算法中。如在文献[15]中，聚类问题被建模成超图划分问题；文献[16]通过模糊逻辑建模来优化聚类算法；文献[17]将聚类建模成混合线性规划问题来进行优化。

2） 簇头选择：如何在众多节点中选择一个节点作为某个簇的簇头。一种简单的簇头选择方式为随机选择，如上述LEACH算法^[14]，但其主要是针对小型单跳传感网，即传感网中的每个节点都与其他节点直接通信，并不适用于大型无线传感网。2004年，Younis等^[18]提出了HEED算法，该算法可以应用于多跳无线传感网，可根据节点剩余能量和均衡负载选择簇头。还有一些分簇算法基于延时^[19]、密度^[20]、位置^[13]等实现簇头选择。

3） 中继节点选择：在大型无线传感网络中，簇头通常远离汇聚节点，需要选择一个最优的下一跳节点来传递整合的数据包。2014年，Tarhani^[21]提出SEECH算法，将具有较多邻节点的节点（即节点的度较高）作为簇头，而将度较低的节点作为中继节点，通过这种方式将负载在不同的节点进行分配，实现负载均衡。

4） 再分簇（re-clustering）：因簇头节点消耗的能量远远大于其他节点，而一旦簇头节点能量耗尽，其所在簇将不能再工作，因而需要周期性地对网络进行分簇，称为再分簇。由于无线传感网需要定期重新选取簇头以保证网络寿命^[13]，为了减少用于再分簇的能耗，再聚类的频率应尽量低，而其涉及的范围应尽可能小。文献[22]提出根据节点的能量情况来动态地触发再分簇流程，避免固定间隔方式中非必要的再分簇造成的能量浪费。

5） 路由优化：在文献[23]中，Verma等提出了一种基于蚁群聚类技术的最优路径路由算法，利用多路径路由方案实现冗余备份；文献[24]主要是为多汇聚节点的无线传感网提供可靠路由。

6） 热点问题：所有的数据包都被发送给汇聚节点，因此汇聚节点附近的节点将成为热门节点，这些热门节点如果不进行负载均衡，很容易比其他节点更早死亡。UCR^[25]和UCS^[26]算法致力于聚类中的热点问题，主要思想为通过降低簇内通信成本补偿高簇间通信负载。

另外，如何避免能量浪费也是分簇算法的研究重点之一。无线传感网中的能量浪费主要是通信干扰和无用侦听等原因造成的。基于TDMA的网络可以避免以上原因导致的能量浪费。在文献[10,11]中，作者均采用TDMA方式组织簇内通信，但没有考虑簇间通信干扰。为了消除来自其他簇的通信干扰，研究人员提出了混合介质访问技术，如LEACH^[14]采用TDMA和CDMA（code division multiple access）相结合的方式，即簇内通信利用TDMA方式，不同的簇分配不同的CDMA码，通过不同的CDMA码避免簇间干扰。同理，将FDMA（frequency division multiple access）和CDMA结合也可以提供无干扰通信^[27,28]。以上混合接入方式避免了通信干扰，但计算能力有限的传感器节点很难同时支持两种接入方式。一种替代的解决方案是给不同簇分配不同的时间段，即采用簇内TDMA+簇间TDMA方式。在文献[12]中，作者提出对文中潜在冲突域内的簇采用不同的通信周期，但是这种方法的缺点是缺少可扩展性，并且效率较低。文献[29]提出将不同簇的通信周期划分问题简化为图论中的着色问题，相邻簇分配的周期不一样，即颜色不一样，然而这种方法的缺点是需要所有的簇都同步。

和之前的研究不同，本文算法同时优化网络能耗和网络覆盖，将网络划分为无通信干扰的簇，时隙分配非常简单，且因为所有的簇都可同时传输，网络性能也大大提高。

2　 本文算法

为了实现无线传感网的无干扰分簇，需要对网络中的节点进行角色分配，即选择簇头节点、成员节点和孤立节点。下文首先对分配规则进行描述，通过这些规则可以实现无干扰分簇。在满足这些规则的条件下，可以将网络划分成不同的簇，不同划分情况下，网络的性能不同；然后，描述本文算法的目标性能；最后提出IFCA，此算法针对两项性能目标，结合分簇规则，实现了无干扰分簇的优化。

2.1　无干扰分簇规则

为了实现簇间通信无干扰，任何一个成员节点的通信范围只能覆盖其簇头节点，而不能覆盖其他簇头节点。为了实现以上目标，节点的选取必须符合特定的分簇规则。本文算法生成的簇为单跳的簇，即所有的成员都可以直接和簇头进行通信，方便时隙分配。本文中的无干扰是指各个簇的数据采集传输（即从成员到簇头的传输）不会形成干扰，而不考虑其他传输是否形成干扰。需要注意的是，数据采集传输是传感网的主要传输方式。

首先通过一个简单的网络拓扑图（如图1（a））分析如何进行无干扰分簇。在图1（a）中，任何一个节点都可被选举为簇头，但是如果希望生成无干扰的簇，必须遵从以下3点规则：

1) 选取的簇头之间至少需要三跳。例如，如果节点1和5被选作簇头（如图1（b））,两个簇之间没有通信干扰，但是在这种情况下，节点7和8必须设定为孤立节点，因为这两个节点中任何一个节点成为簇头，都会造成成员节点6同时覆盖至少两个簇头，产生通信干扰。

2) 选取的簇头可以是一跳邻居，例如，节点1、5、6被选为簇头，节点5、6是一跳邻居（如图1（c）），生成的簇不会产生干扰，因为没有任何一个成员节点会同时覆盖多个簇头。

3) 选取的簇头如果是两跳邻居，则它们的公共邻居必须被设为孤立节点，例如，在图1（d）中，节点4、6被选为簇头，则其公共邻节点5必须被设定为孤立节点。

综上所述，为了实现无干扰分簇，簇头的选举应该遵循以下规则：簇头之间应该没有公共邻居，或者有公共邻居的节点被选举为簇头之后，这些公共邻居必须被设置为孤立节点。以上规则限定了一个节点只能被一个簇头覆盖，因此成员节点和簇头的通信将不会干扰到其他簇，所以生成的簇不会存在簇间通信干扰。

另外，从图1的分析也可得出：同一网络可生成不同的无干扰簇。那么新的问题是，哪种分簇最好呢？ 显然，不同分簇情况下，网络的性能不同，如果性能目标是最小化簇的数目和孤立节点数目，则图1（e）为最优分簇。故在下节中，将定义本文算法的两个性能目标——能耗和网络覆盖，本文算法将根据这两个目标来实现最优的无干扰分簇。

2.2　无干扰分簇的性能目标

本文算法的性能目标是在实现无干扰分簇的同时，使得网络的能耗和覆盖最优。其中，网络能耗主要指簇内通信能耗、簇间通信能耗和数据聚合能耗；网络覆盖是指传感网区域定义的监测点被传感器覆盖的情况。

2.2.1　最优化能耗

根据能耗的含义，定义能耗目标函数如下

F_e=e_{\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{a}}+e_{\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}}+e_{\mathrm{a}\mathrm{g}}(1)

其中，e_{\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{a}}表示簇内通信能耗，其表达式为

e_{\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{r}\mathrm{a}}=\stackrel{\mathrm{c}\mathrm{n}}{\sum _{i=\mathrm{1}}}\sum _{j\in c_i}{e}_j^{\mathrm{s}}+\stackrel{\mathrm{c}\mathrm{n}}{\sum _{i=\mathrm{1}}}{e}_i^{\mathrm{r}}(2)

式中，\mathrm{c}\mathrm{n}是簇的个数，c_i是第i个簇的成员数量，e_j^{\mathrm{s}}是成员j向簇头发送数据包消耗的能量，e_i^{\mathrm{r}}是簇头i接收数据包消耗的能量，式中的第一项是所有的成员节点发送数据包的能耗总和，第二项是簇头接收所有数据包的能耗总和。

e_{\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}}表示簇间通信能耗，即所有的簇头节点将聚合后的数据发送给sink节点需要的能耗，其表达式为

e_{\mathrm{i}\mathrm{n}\mathrm{t}\mathrm{e}\mathrm{r}}=\stackrel{\mathrm{c}\mathrm{n}}{\sum _{i=\mathrm{1}}}{e}_{i\to \mathrm{s}\mathrm{i}\mathrm{n}\mathrm{k}}^{\mathrm{s}}(3)

其中，e_{i\to \mathrm{s}\mathrm{i}\mathrm{n}\mathrm{k}}^{\mathrm{s}}是簇头i向sink节点发送一个聚合数据包消耗的能量。

e_{\mathrm{a}\mathrm{g}}是数据聚合能耗，其表达式为

e_{\mathrm{a}\mathrm{g}}=\stackrel{\mathrm{c}\mathrm{n}}{\sum _{i=\mathrm{1}}}{e}_i^{\mathrm{a}}(4)

其中，e_i^{\mathrm{a}}是簇头i聚合的从成员节点处接收到信息所消耗的能量。

2.2.2　最优化网络覆盖

为实现最优化网络覆盖，首先，假设网络里有n个监测点，每个传感器可以监测的范围是以自身为中心，半径为r的圆；然后，假设每个监测点被k个传感器覆盖（监测）是最优的，即少于k个节点会造成覆盖不足，多于k个节点会造成额外覆盖，定义目标覆盖函数F_{\mathrm{c}}为惩罚函数，即覆盖不足和额外覆盖都会带来消耗，最优化此目标函数即对此函数最小化。

(5)

其中，D是被监测点的集合；\mathrm{c}{\mathrm{v}}_j是实际覆盖监测点j的传感器数目；\mathrm{1}(\cdot )是指示函数;表示节点覆盖不足惩罚，P_{>}代表节点额外覆盖惩罚。

2.3　算法描述

为了同时优化以上两个目标函数，采用基于遗传算法的NSGA-Ⅱ（Non-dominated sorting genetic algorithm Ⅱ）算法^[30]，即将此算法应用到无干扰分簇中，通过算法的迭代，最终生成的无干扰分簇可同时实现优化能耗和网络覆盖。为了应用此算法，定义二进制染色体，即染色体由比特位组成，每个比特代表一个节点，“1”表示此节点为簇头，“0”表示此节点非簇头，则有n个节点的网络可定义为由“0”和“1”组成的n个比特。如图2所示，基于NSGA-Ⅱ的分簇算法通过多轮初始化个体算法，生成初始群体P；在P的基础上进化和变异,生成新的群体Q；再对P、Q进行非支配排序，选取前N个个体，作为新一轮的P，再次迭代。

2.3.1　初始化阶段

初始化个体（染色体）阶段最重要的步骤是从节点中选择簇头。因为簇头的能量消耗比成员节点大得多，因此需要定义一个阈值，并规定只有剩余能量高于阈值的节点才可以成为簇头。阈值的选取会影响分簇的性能，如果阈值太小，会造成频繁地再分簇；反之，如果阈值太大，会使得簇头的选择范围变小，形成的簇并不是最优的，也会降低性能。但如何设定最优的阈值并不是本文的研究重点，我们将在后续工作中研究最优阈值问题。

在本文的仿真实验中，依据实验经验，将阈值设定为初始能量的10%。为了简化筛选程序，选择的所有簇头之间至少有三跳距离，显然这样形成的簇不会产生干扰（符合2.1节中无干扰分簇的第一规则）。为了实现以上簇头选择方案，当一个节点被选为簇头时，它的一跳和两跳邻居要从簇头候选队列中删去，初始化步骤如下：

1） 所有能量超过阈值的节点都被设置为簇头候选点；

2） 随机从簇头候选节点中选择簇头；

3） 被选中簇头的直接邻居成为这个簇的成员节点，并从簇头候选列表中删去；所有的两跳邻居节点因不能再被选取为簇头，所以也从簇头候选列表中删去；

4） 重复步骤2、3直至候选簇头列表为空；

5） 非簇头和非成员节点都被设置为孤立节点。

初始化个体（染色体）阶段算法如算法1所示。其中，Graph为整个节点结构图；Threshold为阈值；ArrayOfNode是每个节点的剩余能量；Candidate是候选节点；Probability是随机成为簇头的概率；StateOfNode是各节点的初始化后的状态，包括Head（簇头）、Member（成员）和 Isolated（孤立节点）。

算法1 初始化个体阶段算法

输入： Graph; Threshold; ArrayOfEnergy

输出： StateOfNode

1 function INITIALIZE (Graph,Threshold,ArrayOfEnergy)

2 Candidate ← {}

3 StateOfNode ← {}

4 for Node ϵ Graph.node do

5 if ArrayOfEnergy[Node]>Threshold then

6 Candidate ← Candidate + Node

7 end if

8 end for

9 while Candidate do

10 for Node ∈ Candidate do

11 if RANDOM() < Probability then

12 StateOfNode[Node] ← Head

13 Candidate←Candidate-Node.neighbor

14 for MemberOfNode ∈ Node.neighbor do

15 StatefNode[MemberOfNode]←Member

16 Candidate ← Candidate - MemberOfNode.neighbor

17 end for

18 end if

19 end while

20 for Node ϵ Graph.node do

21 if StateOfNode[Node]!=Head or Member then

22 StateOfNode[Node] ← Isolated

23 end if

24 end for

25 return StateOfNode

26 end function

2.3.2　进化和变异阶段

在进化和变异阶段，利用群体P₀进行二进制交叉和变异操作，产生下一代同样有N个个体的群体Q₀。二进制交叉操作步骤如下：

1） 从P₀中随机选取两个个体（染色体）；

2） 在2到n-1中随机选取一个整数m；

3） 交换两个个体第m个节点的值；

4） 重复步骤1~3直至产生N个交叉个体。

在完成交叉操作之后，执行变异操作。给每个节点分配一个变异概率，成员节点和孤立节点（比特位的值为0）可以转变为簇头（比特位的值为1），反之亦然。然而，由于在前文中强调过，只有剩余能量高于阈值的节点才能从状态0转为状态1。交叉和变异操作之后形成了具有N个个体的新群体Q₀，其中每个个体对应一个分簇结果。基于个体形成簇的过程如下：所有比特值为1的节点成为簇头，其邻居成为其成员。如果两个簇头具有共同邻居，则这些邻居设置为孤立节点，所有其他节点也被设置为孤立节点。

进化及变异阶段算法如算法2所示。其中，MaxNumOfCycles为最大循环次数；N为群体中个体数量；P为当前群体，Q为生成的下一代群体；R则是在P和Q中选取最优的N个个体，进入下一轮迭代。

算法2 进化及变异阶段算法

输入： MaxNumOfCycles

输出： R

1 function EVOLUTION and MUTATION ALGORITHM (MaxNumOfCycles)

2 Initialize N individuals as P

3 for i = 0 → MaxNumOfCycles do

4 Q ← {}

5 for i = 1 → CEIL(N/2) do

6 m ← RANDOM(2~n-1)

7 Exchange values at the m.th on two randomly selected individuals

8 Q ← Q + selected individuals

9 end for

10 for Individual ∈ Q do

11 for Node ∈ Individual do

12 Flip the state of a node by probability

13 end for

14 end for

15 R ← P + Q

16 R ← NON-DOMINATIONSORT(R)[1:N]

17 P ← R

18 end for

19 return R

20 end function

3　 仿真和结果分析

本节将利用本文算法进行仿真实验，以分析节点数量、监测点的数量、节点的通信半径和节点的覆盖半径对本文算法划分网络分簇的结果及无干扰分簇后网络覆盖的影响。其中，覆盖半径代表节点的监控能力（监控区域是以节点为中心，以覆盖半径为半径的圆形区域）；通信半径代表节点的通信能力。假设节点和监测点均随机分布在1 000 m\times1 000 m的网络中。

如图3（a）所示，无线传感网中分布了200个节点。经过本文算法进行无干扰分簇后，得到的分簇情况如图3（b）所示。由图3（b）可以看出,一个成员节点只被其簇头覆盖，也就是说，当任一成员节点和其簇头节点通信时，并不会干扰其他簇头节点，因此任何两个簇之间不会存在通信干扰。

3.1　节点数量的影响

首先，设置监测点为100个，节点的覆盖半径是30 m，通信半径是50 m，通过改变节点总数（从500个增加到2 300个）分析分簇后簇的总数目（即簇头节点数目）、成员节点数目、孤立节点数目以及无覆盖监测点数目变化情况。其中，孤立节点不参与数据采集，只有簇头节点和成员节点参与数据采集，所以簇头节点和成员节点被称之为活跃节点。从图4（a）中可以看出，随着节点数的增加，簇的数目并没有变化，稳定在150个左右，但是孤立节点和成员节点数量随着节点数的增加而不断增加。图4（b）表示无覆盖监测点数量随节点数量的变化。其中，无覆盖监测点是指那些没有被任何传感器覆盖的监测点，显然这些监测点越少越好。因为IFCA分簇通常会将部分节点设置为孤立节点，所以无覆盖监测点的数量会增大。与分簇前的无覆盖监测点数量相比，当总节点数量约为500时，IFCA分簇会增加约7个无覆盖监测点；当总节点数量增加到2 300时，仅仅增加了约5个无覆盖监测点。图4（a）和 图4（b）表明，当节点数目增加时，每个簇会拥有更多的成员节点，也就是更多的节点参与对监测点的监测，使得无覆盖监测点数目降低，即网络覆盖更广泛，所以本文算法对于密集网络更有效。

3.2　监测点数量的影响

将节点数目固定为2 000个，改变监测点的数目（从20个增加到200个），以分析算法性能。由图5（a）可知，分簇结果（簇的数目、成员节点数目、孤立节点数目）随着监测节点数量的增加，基本保持不变。可能的原因是IFCA为保证无通信干扰，无法增加活跃节点，同时必然会带来更多的无覆盖监测点（如图5（b））。

3.3　节点通信半径的影响

将节点的通信半径从20 m增加到100 m，分析节点通信半径对本文算法划分网络分簇的结果及无干扰分簇后网络覆盖的影响（监测点数设为100个）。如图6（a）所示，节点的通信半径影响了分簇结果，随着通信半径的增大，簇数目在减少，成员节点数目基本保持不变，孤立节点数目增加。这是因为本文算法将无线传感网络划分为没有交集的一跳点集合，通信半径增大使得每个簇的范围变大，所以簇的数目会减少，单个簇内成员节点数会上升。同时，通信半径的增大，也意味着一跳距离的增大，簇之间的干扰范围增大。在此情况下，选择一个簇头的同时就会有更多节点从簇头候选队列中剔除，使得孤立节点增多，成员节点数呈下降趋势。又由于单个簇的范围增加，正负作用相抵使得成员节点数基本保持不变。

图6（b）表明随着通信半径增加，无覆盖监测点的数量也在增加。主要原因包括两个方面：一方面，簇数目减少导致网络中活跃节点数目减少，所以无覆盖监测点的数量增多；另一方面，通信半径的增加会导致部分区域不被任何簇覆盖，称之为空白区域。显然，空白区域的增加会导致无覆盖监测节点数量的增加。

3.4　节点覆盖半径的影响

设置节点通信半径为50 m，探讨节点覆盖半径对本文算法划分网络分簇的结果及无干扰分簇后网络覆盖的影响。由图7（a）可知，随着节点覆盖半径的增加，孤立节点和簇的数目增加，成员节点数量减少。这是因为随覆盖半径的增加，IFCA有更多机会决定节点是活跃还是孤立状态，为了减少通信开销，IFCA会将靠近簇头的节点设置为活跃状态（和簇头距离近，通信能耗少），因此簇的范围会减小，从而使孤立节点和簇的数目增多，成员节点数减少。在图7（b）中，随着节点覆盖半径的增加，无覆盖监测点的数量减少，当覆盖半径达到40 m时，所有监测点都被覆盖。

4　 结 语

本文提出了一种基于多目标优化的无线传感网无干扰分簇算法。该算法的特点为：1） 同时优化了网络能耗和网络覆盖；2） 通过在簇生成的过程中应用本文提出的无干扰分簇规则，生成的簇和簇之间不会产生通信干扰。无干扰分簇简化了时隙分配，使得在大型无线传感网中实现既能避免簇内通信干扰又能避免簇间干扰的时隙分配成为可能。同时这种时隙分配的机制使因通信干扰而产生的能耗浪费被避免，进一步降低了网络能耗。通过仿真实验，分析了不同的网络参数（如不同的节点数目、节点覆盖半径等）对本文算法划分网络分簇的结果以及无干扰分簇后网络覆盖的影响。在未来的研究中，我们将进一步研究本文算法的性能，如通过和其他分簇算法比较来进一步分析能耗性能、网络覆盖性能等。

参考文献

[1] YE W, HEIDEMANN J, ESTRIN D. An energy-efficient MAC protocol for wireless sensor networks [C]// Twenty⁃First Annual Joint Conference of the IEEE Computer and Communications Societies. New York：IEEE Press, 2002:1567-1576.DOI: 10.1109/INFCOM.2002.1019408 .

[2] MAMUN Q. A qualitative comparison of different logical topologies for wireless sensor networks [J]. Sensors, 2012, 12(11): 14887-14913. DOI: 10.3390/s121114887 .

[3] BOYINBODE O, LE H, MBOGHO A, et al. A survey on clustering algorithms for wireless sensor networks [C]// 2010 13th International Conference on Network-Based Information Systems. Washington D C: IEEE Computer Society, 2010:358-364.DOI: 10.1109/NBiS.2010.59 .

[4] AKYILDIZ I F, SU W, SANKARASUBTAMANIAM Y, et al. A survey on sensor networks [J]. IEEE Communications Magazine, 2002, 40(8): 102-114.

[5] AL-KARAKI J N, KAMAL A E. Routing techniques in wireless sensor networks: A survey [J]. IEEE Wireless Communications, 2004, 11(6):6-28. DOI: 10.1109/MWC.2004.1368893 .

[6] BASAVARAJ G N, JAIDHAR C D. H-LEACH protocol with modified cluster head selection for WSN [C]//2017 International Conference on Smart Technologies for Smart Nation. New York: IEEE Press,2017:30-33.

[7] JOHN A, RAJPUT A, BABU K V. Dynamic cluster head selection in wireless sensor network for Internet of Things applications [C]//2017 International Conference on Innovations in Electrical, Electronics, Instrumentation and Media Technology. New York: IEEE Press, 2017:45-48.

[8] BEHERA T M, MOHAPATRA S K, MUKJERJEE P, et al. Work-in-progress: DEEC-VD: A hybrid energy utilization cluster-based routing protocol for WSN for application in IoT[C]//2017 International Conference on Information Technology. New York: IEEE Press,2017: 97-100.

[9] VINODHA D, ANITA E A M. A survey on privacy preserving data aggregation in wireless sensor networks [C]//2017 International Conference on Information Communication and Embedded Systems. New York: IEEE Press, 2017:1-6.

[10] HSU T H, YEN P Y. Adaptive time division multiple access-based medium access control protocol for energy conserving and data transmission in wireless sensor networks [J]. IET Communications, 2011, 5(18): 2662-2672. DOI: 10.1049/iet-com.2011.0088 .

[11] SHAFIULLAH G, AZAD S A, ALI A S. Energy-efficient wireless mac protocols for railway monitoring applications [J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(2): 649-659. DOI: 10.1109/TITS.2012.2227315 .

[12] HANZALEK Z, JURCIK P. Energy efficient scheduling for cluster-tree wireless sensor networks with time-bounded data flows: Application to IEEE 802.15. 4/ZigBee [J]. IEEE Transactions on Industrial Informatics, 2010, 6(3): 438-450. DOI: 10.1109/TII.2010.2050144 .

[13] LIN H, WANG L S, KONG R S. Energy efficient clustering protocol for large-scale sensor networks [J]. IEEE Sensors Journal, 2015, 15(12): 7150-7160.DOI: 10.1109/JSEN.2015.2471843 .

[14] HEINZELMAN W B, CHANDRAKASAN A P, BA⁃ LAKRISHNAN 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 .

[15] RHAZI A E, PIERRE S. A tabu search algorithm for cluster building in wireless sensor networks [J]. IEEE Transactions on Mobile Computing, 2009, 8(4): 433-444.

[16] NAYAK P, VATHASAVAI B. Energy efficient clustering algorithm for multi-hop wireless sensor network using Type-2 fuzzy logic [J]. IEEE Sensors Journal, 2017, 17(14): 4492-4499.

[17] USTER H, LIN H. Integrated topology control and routing in wireless sensor networks for prolonged network lifetime [J]. Ad Hoc Networks, 2011, 9(5): 835-851.

[18] YOUNIS O, FAHMY S. HEED: A hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks [J]. IEEE Transactions on Mobile Computing, 2004, 3(4): 366-379. DOI: 10.1109/TMC.2004.41 .

[19] THAKKAR A, KOTECHA K. Cluster head election for energy and delay constraint applications of wireless sensor network [J]. IEEE Sensors Journal, 2014, 14(8): 2658-2664. DOI: 10.1109/JSEN.2014.2312549 .

[20] LIAO Y, QI H, LI W. Load-balanced clustering algorithm with distributed self-organization for wireless sensor networks [J]. IEEE Sensors Journal, 2013, 13(5): 1498-1506. DOI: 10.1109/JSEN.2012.2227704 .

[21] TARHANI M, KAVIAN Y S, SIAVOSHI S. SEECH: Scalable energy efficient clustering hierarchy protocol in wireless sensor networks [J]. IEEE Sensors Journal, 2014, 14(11): 3944-3954. DOI: 10.1109/JSEN.2014.2358567 .

[22] NEAMATOLLAHI P, NAGHIBZADEH M, ABRISHAMI S, et al. Distributed clustering-task scheduling for wireless sensor networks using dynamic hyper round policy [J]. IEEE Transactions on Mobile Computing, 2018， 17(2): 334-347.

[23] VERMA A, VASHIST P C. Enhanced clustering ant colony routing algorithm based on swarm intelligence in wireless sensor network [C]//2015 International Conference on Advances in Computer Engineering and Applications. New York: IEEE Press, 2015:150-154.DOI: 10.1109/ICACEA.2015.7164684 .

[24] AGARKHED J, BIRADAR G S, MYTRI V D. Energy efficient QoS routing in multi-sink wireless multimedia sensor networks [J]. International Journal of Computer Science and Network Security, 2012, 12(5) :731-736.

[25] CHEN G, LI C, YE M, et al. An unequal cluster-based routing protocol in wireless sensor networks [J]. Wireless Networks, 2009, 15(2): 193-207.

[26] SOTO S, HEINZELMAN W B. Prolonging the lifetime of wireless sensor networks via unequal clustering [C]// IPDPS 05 Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium. Washington D C: IEEE Computer Society, 2005:1-8.DOI: 10.1109/IPDPS.2005.365 .

[27] GHERAIRI S, OUNI S, KAMOUN F. Optimized TDMA multi-frequency scheduling access protocols for sensor networks [C]//2011 International Conference on Communications, Computing and Control Applications. New York: IEEE Press, 2011:1–6.DOI: 10.1109/CCCA.2011.6031412 .

[28] TOSCANO E, BELLO L L. A topology management protocol with bounded delay for wireless sensor networks[C]// 2008 IEEE International Conference on Emerging Technologies and Factory Automation. New York: IEEE Press, 2008:942-951.DOI: 10.1109/ETFA.2008.4638508 .

[29] HAIGANG G, MING L, XIAOMIN W, et al. An interference free cluster-based TDMA protocol for wireless sensor networks [C]//International Conference on Wireless Algorithms, Systems, and Applications (LNCS 4138. Heidelberg: Springer⁃Verlag, 2006: 217-227.

[30] DEB K, PRATAP A, AGARWAL S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-Ⅱ [J]. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197. DOI: 10.1109/4235.996017 .

基金资助

武汉市应用基础前沿项目(2017010201010117)