基于事件的移动认知无线传感器网分簇算法①

谭 龙,王 方

(黑龙江大学 计算机科学与技术学院,哈尔滨 150080)

无线传感器网络(Wireless Sensor Network,WSN)由大量的传感器节点组成,这些节点密集地部署在一个特定的区域用于收集关于目标或事件产生的数据,并提供各种传感和监测应用程序,作为一种很有前途的数据采集技术,在物联网中得到了广泛的应用,成为重要的基础网络之一[1,2].由于无线业务的爆炸式增长使得未授权的频谱日益拥挤,导致运行在未授权频谱上的无线传感器网络受到了严重干扰.认知无线电(Cognitive Radio,CR)技术已经发展成为解决频谱短缺问题的一种有效方法,它允许对许可频谱进行机会性访问并广泛应用于环境,军事,运输等多个领域[3].无线传感器网络受益于CR 技术的这一优势克服了频谱匮乏的挑战.为此,通过在无线传感器网络中加入动态频谱接入(Dynamic Spectrum Access,DSA)方案,提出了一种新的无线网络模式——认知无线传感器网络(Cognitive Radio Sensor Networks,CRSNs)[4].

CRSN 同无线传感器网络中的固定频谱分配方法不同,节点通过机会主义利用空闲频谱.频谱的机会使用由认知循环操作完成,包括频谱感知、频谱决策、频谱共享和频谱迁移.CRSN 节点通过频谱感知来确定空闲频谱,通过频谱决策来选择它们要使用的频谱,根据主用户(Primary User,PU)的活动进行频谱切换来改变信道[4].尽管CR 技术使用不同频段让无线通信更灵活,但它们也带来了一些问题.第一,动态无线电环境中的路由受限于频谱可用性；第二,认知循环操作会中断传感器节点之间的传输；第三,主用户的活动会影响数据传输的成功率.如果节点是移动的,这些问题会更复杂.节点的移动性导致频繁的拓扑变化.此外,事件驱动的通信特性会导致突发的流量,造成信道冲突和数据包丢失.

本文提出了基于事件的移动认知无线传感器网的分簇算法(Event based clustering algorithm for Mobile Cognitive radio sensor networks,EMC).该算法在事件发生后根据移动节点当前位置和在区域内停留时间来确立合格节点,而后计算簇头权值来选择簇头.设计了直接分簇模式,并进行簇头与成员节点间的连接时间预估计,簇头再根据簇中每个成员移动节点的预估计连接时间以TDMA 方式进行通信,分配给成员节点时隙和空闲信道用来数据传输.这样确保了簇的稳定性,从而提高了数据传输率,并减少了由于簇成员移动变化而带来的控制开销和能量消耗.

1 相关工作

在现有的移动节点分簇算法中,WSN 中分簇算法是比较多比较成熟,WSN 的分簇算法在提高网络性能,延长网络生命周期等方面取得了一些成功.WSN 设计分簇方案目的是以最小能耗收集信息[5].低能量自适应分簇层次移动(LEACH-mobile)算法[6],通过在LEACH协议中加入节点成员声明来支持节点的移动性.传感器在连续两帧期间未接收来自其簇头的请求,就认为自己已离开簇,因此它将广播一个簇加入请求消息,以便加入新簇并避免丢失更多的数据包.因此,LEACHmobile 算法以增加控制开销为代价,提高了包传输的成功率.文献[7]中提出了一种基于移动性度量的LEACH移动增强协议,该协议用于簇头选举,选择一个具有较小移动性的节点成为簇头.文献[8]提出两种基于三层结构的移动WSN 分簇算法,最大限度地减少数据损失和提高能量效率.然而,所有这些分簇方案都假设固定信道分配,它们无法处理频谱感知和信道切换等问题.因此,这些方案不适合CRSNs.

文献[9]提出了一种基于事件的移动认知无线传感网络分簇算法,算法分为两个阶段,首先寻找适合成簇的节点,其次这些节点利用空闲频谱分簇,率先把节点移动性应用到CRSN 当中.文献[10]研究了多信道CRSNs 的动态频谱访问的问题.文中采用了数据包大小可变的自适应技术,来适应可变信道上的传输,更充分利用了传感器的能量.文献[11]提出了一种新的节点选择方案,以提高CRSNs 的协作频谱感知能量效率.除此之外,文中所提出的方案可在一定程度上有效平衡不同传感器之间的能量消耗.文献[12]中提出了一种基于能量感知分簇的CRSN 路由算法(EACRP),该算法同时考虑了能量和动态频谱问题.EACRP 采用自组织分布式成簇,通过产生最佳簇数来获得较少的平均节点功率.为了减轻PUs 的影响,EACRP 形成具有更多共用信道的簇,并在选择用于簇内通信的数据信道时采用协作感测的概念.文献[13]提出了一种用于CRSN 的低能量自适应不均匀分簇层次结构,采用不均匀分簇方法来平衡多跳传输方式下簇头之间的能耗.仿真结果表明,该算法不仅可以有效地平衡簇头中的能量消耗和CRSN中的网络负载,还可以显著延长网络生命周期.

2 系统模型

2.1 网络模型

传感器网络由分布在监测区域内的n个移动传感器节点组成,具体信息：

1)用户：PUs 无限制使用授权信道,次用户(Secondary User,SU)在没有PUs 活动的情况下,可以机会主义访问授权信道；

2)节点：传感器节点具有相同的初始能量、传输范围,并且可以实现空闲频谱的感知.

3)信道：网络中存在M个具有唯一ID 的非重叠正交信道；两个相邻的CRSN 节点如果有共同的信道,则它们是互相连接的；存在一个公共控制信道(Common Control Channel,CCC)用来交换控制信息,并且每个节点通过邻居发现都获得一跳邻居节点及其空闲信道.

4)定位：每个传感器由定位算法计算出自己的二维坐标以及自身速度.

5)移动：传感器节点根据随机航点移动模型而移动[14].

6)时钟：假设节点均时钟同步,且事件结束前非簇头合格节点在其分配的时隙中总有数据要发送到簇头.

通信由事件驱动,位于事件区域内的CRSN 节点检测事件,这些节点生成传递到sink 的数据包.CRSN事件覆盖范围用虚线表示,如果PUs 活跃,则SUs 应该机会主义访问信道,具体过程如图1所示.

图1 航点模型

2.2 随机航点模型

移动节点随机选择一个目标位置,然后从该位置向目标位置移动,速度介于[vmin,vmax]之 间,其中vmin是节点的最小速度,vmax是节点的最大速度.如果节点移动到边界,它将以相同的速度以边界为边进行反射,入射角等于反射角.如果节点移动到目标位置后,将重新选择新的目标位置进行移动,如图2所示.

图2 网络模型

2.3 能耗模型

移动CRSN 节点的能耗主要包括频谱感知、频谱切换、数据传输、数据接收和节点移动的能耗.本文使用eswitch分别表示信道切换的能量消耗,由于信道感知是每个移动节点常见的周期性过程,所以其能量消耗不予考虑.在模拟中不考虑遮蔽损耗的影响,同时假设无线电信道是对称的,本文采用文献[12]给出的无线电能量耗散模型.在该模型中,发射器和接收器之间距离为d的情况下发送和接收k位消息的能耗表示为：

其中,Etran为传输能耗,Erec为接收能耗,eampdε为传输放大器的能耗,其中 ε为传播指数,根据发射器和接收器的传输条件Edis的取值范围在2 到4.Edis为运行发射器或接收器中电路的能耗.本文中通讯能量参数设置为：Edis=50nJ/bit,eamp=10pJ/bit/m2,ε=2.5和eswitch=40mJ.

3 分簇算法

3.1 合格节点的选择

事件区域内的移动节点检测到事件后,自身状态由Snone变为Seligible,表示该节点为合格节点,并向周围一跳邻居节点发送请求消息,邻居节点收到请求消息将返回自己的坐标,事件内的节点选择一个横坐标距离自己最远的非事件区域节点,经事件区域内节点协调,确定一个区间作为合格节点区域.事件区域节点通过公共控制信道将合格节点信息(Eligible Node Information,ENI)发送给它们的单跳邻居节点,ENI 中包含控制字段、节点id、节点位置信息和区域信息.

假设任意节点需要n个时间片来传送数据,且一个时间片长为 τ,那么节点在合格区域内的时间应大于nτ才能保证数据的顺利传输.接收到ENI 的节点发现自己位于该区域内,且其纵坐标比发送者的纵坐标距离sink 更近,并计算自身在区域内停留时间,如果停留时间大于nτ,节点状态变为Seligible.新的合格节点将ENI 发送到自己的一跳邻居,同时区域内的节点如果有一跳邻居位于区域外且正向区域内移动,则该节点状态设置为Sstandby,该过程持续到ENI 到达sink.不符合条件的移动节点不发送ENI 消息,为了不朝sink 以外的方向进一步扩大区域.

移动节点1,2,3 是位于事件区域的节点,通过不在事件区域内节点4 和5 反馈的数据,节点1 发现节点4 的水平位置距离自己最远,同理节点2 发现节点6 的水平位置距离自己最远,由事件区域内节点协调,划分出一个区域,该区域是节点4 与节点6 横坐标区间,如图3所示.

图3 合格节点选择模型图

合格节点确定的EMC 算法以分布式的方式确定合格节点,在此阶段,本文假设传感器节点密度足够大.EMC 算法的步骤如流程图4所示.

图4 合格节点选择流程图

算法1.合格节点选择1：Consider node where is a set of nodes in the network i V 2：if Node detects event then 3：It is eligible for clustering i 4：State()=“Eligible”i 5：sending inquiry request to one-hop neighbors other than event detecting neighbors(x0,x1)6：calculate and select an interval 7：Start sending ENI to one-hop neighbors other than event Detecting neighbors 8：else 9：if It receives ENI from its neighbor then(x0,x1)10：judge whether it is in the internal or not xi∈(x0,x1)11：if then 12：calculate i residence time t in (x0,x1)

13：compare the distance yi,sink≤yENI−sender,sink∧yi,event≥yENI−sender,event∧t＞nτ 14：if 15：then Node i is eligible for clustering 16：State(i)=“Eligible”17：Send ENI to one-hop neighbors 18：end if xi∉(x0,x1)∧i(x0,x1)∧i ＞nτ 19：if direction to residence time then i 20：Node is a candidate for clustering i 21：State()=“Standby”22：else 23：Not eligible 24：end if 25：else 26：Not eligible 27：end if 28：else i 29：Node is not eligible 30：end if 31：end if

3.2 簇头选择

本文使用启发式算法进行簇头选择.簇头选择时充分考虑了频谱可用性、能量损耗、节点移动性等多项因素进行权值处理,最大权值节点作为簇头,选择的参数如下：

1)节点速度(vi−current)：选择速度较低的节点作为簇的簇头.在权重计算中,本文采用公式来选择当前速度尽可能低的节点.

2)节点到sink 的距离(di,sink)：由于收集的数据由簇头进行聚合传递,因此更接近sink 的簇头所消耗的能量越少.

3)剩余能量(Ei)：节点成为簇头后会比普通节点更耗费能量,所以要考虑节点剩余能量.

4)可用信道数(Ci)：可用信道数多的节点成为簇头,会在形成的簇中拥有更多的空闲频谱使用机会.

5)合格节点度(Dei)：具有最多一跳合格节点邻居数的节点更适合成为簇头.

6)节点方向与sink 连线间夹角正切值(A)：选择运动方向靠近sink 的节点,形成的簇更稳定.

根据这些参数,任意节点i进行簇头选择的权值为：

其中,w1+w2+w3+w4+w5+w6=1.在这个过程中,邻域内权值最高的节点成为簇头,剩余节点再次比较权值,此过程将持续到所有节点都成簇头或者簇成员为止.

3.3 公共信道确定

每个簇头检查所有符合条件的单跳邻居中是否存在公共信道.如果存在公共信道,CRSN 中的每个节点感知信道并记录包含每个信道的PU 出现概率(Ppu)和平均信道空闲时间(Tidle)的信道状态表.簇头通过比较具有较低Ppu、较高Tidle和较多一跳邻居节点的公共信道来形成簇.本文给信道a分配一个权值,它有3 个参数,公式如下：

3.4 直接分簇

完成公共信道选择后,簇头将向它邻居节点发送成簇请求(Clustering REQuest,C_REQ),然而,一个节点可以是两个或多个簇头的邻居,但它只能成为一个簇头的簇成员节点.因此,节点只答复给一个簇头.节点会计算与簇头亲密度,该值用于确定节点是否适合连接这个簇头.该值由下面过程得出：

假设在时间t节点i的位置是：

簇头节点j的位置是：

本文将节点接收来自一个簇头消息的时间设置为t=0,因此有：

其中,Rtran代表节点的通信范围.如果节点i在时间t仍在簇j中,有：

Δti,j表示节点i和节点j的估计连接时间,可以由式(8)求出,式(8)的解有两个分别为t1、t2,如果max{t1,t2}≤0,则Δti,j=0；否则 Δti,j=max{t1,t2}.

本文在分簇时采用文献[15]所提出了直接分簇方式.在无向分簇方式中数据传输需要先传给簇头,簇头会聚合数据然后发给下一跳簇头或网关,如图5(a)所示,这会导致节点通讯开销大,能耗高,网络寿命短.相反,沿着数据在事件到sink 的传播方向上分簇,这样确保数据一直向着sink 方向传输而不会回传,如图5(b)所示.

图5 分簇方式

其中,λ1+λ2=1.

在节点选择完簇头之后,它将发送一条确认信息(ACKnowledgement,ACK)来回复簇头.如果一个非簇节点没有收到来自相邻簇头的任何请求,它自己成为一个簇头.算法2 描述了直接分簇算法,如算法2 所示.

算法2.分簇算法1：if State(j)=“CH” then a∈C j 2：for do Wa 3：calculate 4：end for 5：send C_REQ message to the nodes through channel 6：wait for ACK message from the nodes 7：else 8：if State(j)=“Eligible Node” and it receives C_REQ message then Wij a 9：calculate 10：join the cluster whose is the biggest 11：send ACK message to the selected CH j Wij 12：if State()=“Eligible Node” and it did not receive C_REQ message then j 13：State()=“CH” goto 1 14：end if 15：end if 16：end if

3.5 簇维护

由于传感器节点的速度或方向突然变化、传输过程中的网络拥塞或硬件故障造成的,因此在传输过程中需要加入确认消息(ACK).

在成功接收到数据包后,簇头将向非簇头合格节点发送ACK 消息.如果合格节点收到ACK 消息,它将确认数据包已成功传输,如果合格节点未收到ACK 消息它将广播簇加入请求消息.收到簇加入联合请求消息时,簇头将像在第二阶段那样向该节点传输簇头消息.

另外,由于簇头节点和簇成员节点都保留了估计连接时间的信息,所以它们都可以检查簇成员节点在下一个时隙是否会留在簇中.如果簇成员节点不打算留在簇中,它将广播一条请求消息以加入一个新簇.然后,簇头将删除该簇成员节点.

图6演示了合格节点离开旧簇并加入新簇的过程.节点5 加入簇J,而节点9 离开簇.簇J 的簇头将节点9 从TDMA 计划中删除,并将节点5 添加到TDMA 计划中.TDMA 调度是基于簇成员节点和簇头节点之间的估计连接时间 Δt按升序排序的.新的TDMA 时间表可能具有如图7所示的形式,节点9 被节点5 替代,而不会影响到数据传输.

图6 簇维护模型图

图7 TDMA 时间片

4 实验分析

本文在Matlab 2018b 中建立了一个仿真环境来研究EMC 分簇算法性能.本文主要从分簇所需要的时间,连通性和分簇过程中的能量消耗这3 个方面对协议进行了仿真测试,实验中改变的参数是事件到sink的距离、事件区域半径R以及节点的传输半径r.本文同mESAC[9],MNB[16],EACRP[12]这3 种算法进行了比较.在模拟中,权重系数取值为w1=0.2,w2=0.1,w3=0.1,w4=0.3,w5=0.2,w6=0.1,λ1=0.8,λ2=0.2,表1为实验中用到的参数,本次实验的拓扑图如图8所示,黑点为 簇头,灰点为簇成员.

表1 模拟参数

图8 分簇结果拓扑图

本文定义成功的数据包传递率为Rpdr,平均控制开销为Oavg,如下所示：

其中,Nrec为 成功传递的数据包数目,Nlost为丢失据包,Ototal为合格区域内总控制开销.

4.1 成簇时间

建立簇需要一些时间,时间长短取决于合格区域的建立、簇头的选择、节点通讯范围等.从图9中可以看出,mESAC,EACRP 与MNB 需要更多的分簇控制包交换,因此它们形成簇需要更多的时间.分簇所需要的时间随着事件半径的增加而增加,如图10所示,EMC 分簇需要的时间相比于mESAC,EACRP 与MNB 分别提升了1.18 倍,2.81 倍和7.18 倍.

图9 控制包数目对比图

图10 成簇时间对比图

4.2 连通性分析

图11表示了在不同传输半径下,4 种算法的连通性.观察可以看出EMC 的连通性更好,这是由于在EMC 中,采用直接分簇办法,让数据包沿单向传输,避免了数据回传的问题,并且选择信道数目多的节点成为簇头,同时考虑了簇成员节点与簇头的连接时间,减少了数据包不必要的丢失.而算法MNB、EACRP 和mESAC 没有考虑节点连接时间,在节点离开后容易造成数据包丢失.因此EMC 的连通性相比于mESAC,EACRP 与MNB 分别提升了1.07 倍,1.63 倍和2.09 倍.

4.3 分簇能耗

CRSN 节点的电池电量有限,能耗是本文算法重点考虑的因素.通过仿真实验得到,事件发生区域到sink 的距离和节点传输半径对分簇能量的影响,节点传输半径增加导致有更多的节点参与到分簇过程中,因此会消耗更多的能量.MNB 形成簇需要3 个步骤,每个节点在每一步都会通知它的邻居节点,这会导致额外的能耗.并且MNB 和EACRP 在分簇过程中是所有节点均参加分簇,这会导致能耗必然高于EMC 和mESAC.再由图9可以看出,mESAC 控制包的数量略高于EMC.如图11所示,EMC 的分簇能耗同其他算法相比能耗有明显的优势.图12为分簇能耗对比图.图13为EMC 分簇过程中簇头能耗与节点能耗对比,簇头能耗较高,并且节点是移动的,所以要在每一轮重新进行簇头选择.

图11 连通性对比图

图12 分簇能耗对比图

图13 簇头与节点能耗图

5 结论

分簇是一种提高动态网络拓扑稳定性的重要方法.针对认知无线传感器网中移动节点能耗不均,连通性不佳的问题,本文中通过计算移动节点在合格区域的逗留时间以及节点在簇中的连接预估计时间,并采用直接分簇算法来解决移动CRSN 对于事件到sink 协调方案的问题.同时给出分簇的维护机制,通过TDMA方式来协调事件和sink 之间的通信.仿真结果表明,EMC 算法在连通性、分簇时间和分簇能耗方面均有明显提高,能更好地适应移动场景.