面向通信扇区优化的有向传感网络簇路由

张 驰

(河南财经政法大学 计算机与信息工程学院，河南 郑州 450046)

0 引 言

目前，有向传感网络(directional sensor networks，DSNs)[1,2]在智慧城市中广泛使用。DSN网络是由微型的有向传感节点(directional sensor nodes，DNs)组成。通过DNs覆盖目标，并感知目标状态，再将数据传输至基站(信宿)，进而实现对监测区域的目的。

与全向传感节点不同，有向传感节点的通信区域和感测区域具有方向性[3]。通常，DNs的通信半径是有限的，且由电池供电。因此，DN需通过多跳才能将数据传输至基站。

通过分簇算法，将网络划分为层次化结构，有利于提高数据传输效率和网络连通率，进而节省网络能量。每个簇有一个簇头(cluster head，CH)，簇头收集本簇内的节点(简称簇成员)数据[4]。簇头通过网关节点将数据传输至基站(base station，BS)。现存的分簇算法多数是针对全向传感网络，它们都没有考虑到DNs的特性，如有限的工作方向、窄小的通信视角。因此，将这些分簇算法直接应用于DSNs[5-7]，难以获取良好的网络性能。

目前，只有少数文献研究了DSN网络的分簇问题。文献[8]提出自动分簇算法(autonomous clustering algorithm，ACA)。但是，ACA算法最初在选择簇头时，并没有考虑节点能量。只是在后续簇头更新时，考虑了节点剩余能量。文献[9]提出了基于目标覆盖的分布式分簇(target coverage-based distributed clustering，TDC)算法。TDC算法在选择簇头时，考虑了节点密度、剩余能量以及离基站的距离。

然而，上述算法并没有考虑到DNs朝向基站的扇区问题。实质上，优先选择朝向基站的扇区内节点作为簇头，可能会提高数据包传输效率。

为此，提出面向通信扇区优化的簇(communication sector optimization-based clustering，CSOC)路由。CSOC路由先从扇区角度，构建候选扇区集，再从候选扇区集中择优选择簇头。簇头间再选择网关，进而构建头的数据传输路径。仿真结果表明，提出的CSOC路由降低了能耗，减少了数据传输路径。

1 系统模型及假设

1.1 DN的感知和通信模型

图1 有向传感器感知和通信模型

令(xi,yi)表示DNsi的位置坐标。对于位于(x,y)位置的目标b，若满足式(1)，则目标b在节点si覆盖范围内

(1)

1.2 DN节点扇区特性

随着电子技术的发展，DN的感知方向可以绕定点旋转。即DN可以有多个扇区。当然，在特定时刻，只有一个扇区在工作。因此，假定DN有Ωc、Ωs个通信扇区、感知扇区。用(Fk,Fk+1)表示第k个通信扇区的两条边线，且k∈Ωc。类似地，用(Gk,Gk+1)表示第k个感知扇区的两条边线，且k∈Ωs。图2显示了Ωc=Ωs=6的节点扇区示例。

图2 扇区示例

2 CSOC路由

CSOC路由通过考虑节点的扇区信息、节点能量以及离基站距离，选择最优的簇头和网关。先寻找候选扇区，再计算候选扇区的权重值。然后, 再考虑节点的能量、距离信息选择簇头。再依据簇头，选择网关。

2.1 候选扇区

以快速传输数据、减少通信跳数为原则构建候选扇区。尽量选择扇区指向基站的节点作为簇头。因此，将指向基站的扇区纳入候选扇区。引用布尔变量bi,k。若bi,k=1，表示节点si的第k个通信扇区指向基站；反之，该扇区未指向基站。

对于任意节点si，其有Ωc个通信扇区。将节点si与基站位置连成线sib。对于任意一个扇区k∈Ωc，若sib与扇区边线Fk、Fk+1的两个夹角只要有一个小于90度，该扇区i,kF就纳入候选扇区集ψc。

具体而言，对于节点si的扇区i,kF，若满足式(2)，则将i,kF加入ψc

(2)

如图3所示，节点si的扇区i,2F的边线F2、F3与sib的两个夹角为∠biF2、∠biF3。依据式(2)，扇区i,1F、i,2F、i,3F和i,6F可纳入候选扇区集ψc。因此，bi,1=bi,2=bi,3=bi,6=1。

图3 构建候选扇区的过程

2.2 节点权值

从图3可知，位于不同扇区内的节点向基站传输数据的路径并不相同。应先从扇区角度，选择最优扇区，再选择簇头。为此，先计算候选扇区ψc内扇区的权重值。令Wi,k表示节点si的第k个的权重值

(3)

再针对节点扇区的权重值，并考虑节点的邻居节点、距离以及能量信息，产生簇头。令Qi,k表示位于以扇区k作为与基站的通信区的节点i成为簇头的概率

(4)

(5)

(6)

(7)

2.3 簇头选择及簇形成

依据式(4)计算Qi,k后，再根据式(8)产生簇头。即将具有最大Qi,c值的节点成为簇头

(8)

若满足式(8)，就宣告自己成为簇头。并向邻居节点广播通告消息Ann_CH。Ann_CH消息内包含了簇头的ID号以及工作的通信扇区。

收到Ann_CH后(假定节点si为簇头，其工作的通信扇区为k)，说明已有节点成为簇头。据此，邻居节点sj∈ni,k就加入该簇，以节点si为簇头。

2.4 网关的选择

簇头间通过网关通信。因此，每个簇头先利用式(9)构建候选网关节点集

i←j|(sj∈Mi)&(sh∈nj,k&sh∈M)

(9)

(10)

2.5 簇头更新

在CSOC路由中，簇头负责向基站传输数据。因此，相比于其它节点，簇头的能耗速度可能更快。为此，需要对簇头进行更新，避免簇头能量过低，甚至消耗殆尽。

当簇头的能量低于预定阈值Eth时，就重新启动簇头的选择过程。考虑到所有节点的能量逐步减少，对阈值Eth进行动态调整，每执行一次簇头选择，阈值Eth就降低一部分

Eth=Eth，0<<1

(11)

3 性能分析

3.1 仿真环境

在区域1000 m×1000 m内部署200～1000个节点，目标数为50～200个目标。通过NS-2仿真软件构建仿真平台[11]。具体的仿真参数见表1。

表1 仿真参数

为了更好地分析CSOC路由性能，选择同类路由TDC进行比较。选择覆盖目标数-簇率(coverage targets-cluster ratio，CTCR)、系统开销率、网络寿命以及平均路径跳数。覆盖目标数-簇率等于所覆盖的目标数与簇的比例。该值越大，说明性能越好。

3.2 目标数-簇率

首先分析节点数对目标数-簇率的性能影响，其中节点数从200至900变化，每个节点的扇区数为4。目标数为120。

图4 节点数对目标数-簇率影响

图4显示节点数对目标数-簇率的影响。从数据显示，最初节点数的增加，目标数-簇率快速下降。但当节点下降至400后，目标数-簇率下降速度变缓。这符合预期，在目标数固定的情况下，节点数越多，所形成的簇越多，目标数与簇数的比值自然越小。相比于TDC，提出的CSOC路由的目标数-簇率得到提升，平均约提升至1.2。

3.3 网络寿命

本小节，分析节点数和目标数对网络寿命的影响。采用文献[12]的定义，将部署网络开始时间t0至网络内出现第一个能量消耗殆尽的节点时间t1的差，即将t1-t0作为网络寿命。

图5显示了目标数为120、每个节点的扇区为4时，节点数对网络寿命的影响。从图5可知，节点数的增加，提升了网络寿命。原因在于：节点数越多，网络的总体能量越高。相比于TDC，CSOC路由的网络得到提升。原因在于：CSOC路由优化了簇头选择，平衡了网络能耗。

图5 节点数对网络寿命的影响

图6显示了节点数为600、每个节点的扇区数为4时，目标个数对网络寿命的影响。从图可知，在节点数一定情况下，目标数的增加，降低了网络寿命。这符合逻辑。目标数的增加，就需要更多节点覆盖目标，这就加大了能量消耗。

图6 目标数对网络寿命的影响

3.4 系统开销率

先分析系统开销率随节点数的变化情况，如图7所示，其中目标数为100，每个节点的扇区数为4。

图7 节点数对开销率的影响

从图7可知，节点数的增加提升了系统开销率。原因在于：节点数越多，需要交互的控制包就越多，这必然增加了开销率。与TDC算法相比，CSOC路由控制了开销率。

图8显示了节点数为300时，目标数为120时，节点扇区数对开销率的影响。从图8可知，扇区数的增加使开销率呈上升趋势。这主要是因为：节点扇区越多，选择候选扇区以及簇头越复杂，所产生的开销就越多。与图7类似，相比于TDC，CSOC路由仍控制了开销。

图8 扇区数对开销率的影响

3.5 路径跳数

最后，分析节点数对路径跳数的影响，如图9所示，其中目标数为120，每个节点的扇区数为4。

图9 节点数对路径跳数的影响

从图9可知，最初(节点数从200至400变化期间)，路径跳数随节点数的增加，快速下降。但当节点数增加至400后，路径跳数随节点数增加而下降的速度变缓。原因在于：节点数越多，节点密度越高，可选的数据传输路径越多，进而产生最短路径的可能性越大。相比于TDC，CSOC路由控制了路径跳数。

4 结束语

簇结构是提高数据传输效率，减少能耗的有效策略。为此，本文针对有向传感网络，面向通信扇区优化的簇CSOC路由。CSOC路由从通信扇区角度选择簇头。簇头再从两跳邻居节点择优节点网关。仿真结果表明，提出的CSOC路由降低了能耗，延长了网终寿命。