采用虚拟网格的格头连通的WSNs路由算法

丁 凰， 缪相林， 周建龙， 何绯娟

(1.西安交通大学城市学院,计算机系,陕西 西安 710018；2.西安交通大学 计算机学院,陕西 西安 710049)

0 引 言

无线传感器网络(wireless sensor networks,WSNs)为分布式网络[1]，其由多个微型具有感测能量的传感节点组成。通过这些传感节点感测环境数据，如温度、湿度等，然后将这些感测数据传输至信宿。 然而这些传感节点存在如电池能量和数据处理能力受限等不足[2～3]。由于传感节点经常部署于恶劣环境，给传感节点替换电池成为不可能。因此，充分利用电池的有限能量是WSNs必需解决的问题。

由于传输数据消耗了传感节点的大部分能量，可利用有效的路由算法平衡节点间能耗，进而保存节点能量。目前，研究人员已提出多类的路由，如基于簇类路由[4]、网格路由[5～7]、区域路由[8～10]等。这些协议能够降低节点能耗速度，但其在选择路由时，并没有充分考虑到信宿的移动性，同时也并没有充分利用节点的休眠机制[11，12]。

本文提出基于虚拟网格的格头连通路由(virtual grid head-based grid head connected routing,VGCR)。先将网络划分为虚拟网格，并在每个网格内产生一个节点作为格头，由格头组建数据包传输路径。此外，每个格头设有休眠和活动两种状态。VGCR路由考虑到信宿的移动问题，引用信宿局部格头概念。实验数据表明，提出的VGCR路由有效地保存能量，并提高了数据传输率。

1 网络模型

每个节点利用自己的全球定位系统(global positioning

system,GPS)位置坐标估计自己的GID。假定节点i的位置坐标(X,Y)，则其GID可依式(1)计算

GID(X,Y)={(gi,gj)|gi=[X/l],gj=[Y/l]

(1)

式中 (gi,gj)为网格编号。

图1 网格模型

2 VGCR

VGCR利用虚拟网格传输数据。先在网格内产生一个格头(grid head, GH)，再从多个GH内选择部分GH组建数据传输路径。如图2所示。

图2 数据传输示意

2.1 GH的选择

最初，每个网格内产生一个GH。每个节点随机设置一个定时器[13]。最先定时完毕的节点成为GH，并向其他节点发出通告。收到这些通告的节点，就不参与路由。

此外，每个GH具有活动和休眠2个模式。最初，在无线信道的预定时间间隔内t，每个格头先求gx和gy之和，然后判断这个和是否为偶数，如果是偶数，则此GH进入活动模式(GH_MODE=1),反之，和为奇数的GH就进入休眠状态(GH_MODE=0)。模式切换算法的伪代码如下:

Mode Setting of GH

gridx:xco-ordinate of the grid of the GH

gridy:yco-ordinate of the grid of the GH

GH_MoDe:A GH node operation either active(1)

or sleep mode(0)

t:timer associated with each GH for mode change

for(each GH)

if ((gridx+gridy)mod 2==0)

GH_MODE←1

else

GH_MODE←0

end if

end for

如图3所示，每个网格内有一个GH，并且只有部分GH为激活状态。

图3 格头选择示意

2.2 信宿检测

在WSNs中，节点一旦感测到数据，即向信宿传输数据。由于信宿是移动的，节点需要检测信宿的位置[14，15]。信宿周期地广播Sink_Location包，其包含了自己的gx和gy。一旦接收到Sink_Location包，GH就向信宿回复Beacon包，其也包含GH的gx和gy。信宿接收Beacon包后，即检测并判断它们是否在同一个网格内，如果在同一个网格内，信宿即向格头传输ACK消息。

一旦收到ACK，GH即将自己作为连通信宿的下一跳节点，并成为信宿局部GH(local gh,LGH)。一旦选举了LGH，信宿就丢掉来自邻近GH所发送的Beacon消息。产生LGH的信息交互过程如图4所示。

图4 产生LGH的信息交互过程

然后，LGH广播Sink_Detection包。收到Sink_Detection包的GH就将LGH作为连通信宿路径的下一跳节点。4个邻近的GH再重播Sink_Detection，然后，再以同样的方式选择下一跳转发节点。致使，所有活动状态的GH能够共享连通信宿的路由路径。

2.3 数据传输

一旦传感节点检测到目标事件，其即感测数据，然后成为源节点，并传输数据。首先，广播META_DATA数据包。一旦接收META_DATA包，格头就回复META_DATA_ACK包。如果回复META_DATA_ACK包的是LGH，则源节点就直接将感测数据传输至LGH；否则，将感测数据传输至第一个回复META_DATA_ACK的GH，再由GH选择下一跳转发节点，依次类推，直至数据包传输至信宿。

2.4 对信宿移动的处理

由于信宿不断移动，需频繁地更新LGH。因此，信宿通过周期地广播Sink_Location包，告知自己的位置[16]。而当前的LGH可能是处于活动状态或休眠状态。因此，当信宿收到的Beacon包不是来自当前的LGH，说明当前的LGH是处于休眠状态[17]。为此，信宿必须从当前处于活动状态的GH中选择一个GH作为LGH。

据此，信宿向邻近的GH发送ACK包，第一个接收此ACK包的GH宣称自己为新的LGH。新的LGH再广播Sink_Location包。邻近的GH收到Sink_Location包后，就此发送节点(新的LGH)与原来的LGH进行比较。如果不是同一个节点，就将新的LGH作为自己的下一跳节点，否则丢弃Sink_Location包。

2.5 GH模式的切换

最初，VGCR算法是利用所有虚拟网格数之和的奇偶性决定此GH的模式(活动或休眠)。当执行一段时间(t)后，就必须依据信宿的位置进行模式切换。通过切换GH模式，平衡网络能耗。

经一段时间后，每个GH判断自己是否在当前LGH的邻近网格内。如果不在，则表明信宿已远离自己，此阶段可以进入休眠状态。如果在的话，自己就需进入活动状态。

对于第iGHGHi,如果满足式(2)，则进入活动状态，否则就进入休眠状态

if((GHi→gx==x-1&&GHi→gy==y-1)‖

(GHi→gx==x-1&&GHi→gy==y+1)‖

(GHi→gx==x+1&&GHi→gy==y+1))‖

(GHi→gx==x1+1&&GHi→gy==y-1))

(2)

式中x=LGH→gx,y=LGH→gy。以图5为例，位于LGH的邻近4个网格内的GH需要保持活动状态。

图5 GH模式切换示例

3 性能仿真与分析

3.1 仿真环境

利用Castalia软件器建立仿真平台。考虑的网络区域，传感节点数为200个。信宿移动速度在5，10，15，20，25 m/s变化。信宿依据高斯移动模型移动。节点的初始能量为10 J。仿真时间为120 s。每次实验独立仿真100次，取平均值作为最终实验数据。 为了更好地分析VGCR协议性能，选择EAGER路由[18]作为比较，并重点考查网络寿命、数据包传递率、端到端传输时延和平均能耗的性能,仿真结果如图6。

3.2 网络寿命

本文用活动节点数表征网络寿命。在同一个时间点，活动节点数越多，说明网络寿命越长，实验数据如图6(a)所示。可知，VGCR协议的活动节点数优于EAGER协议。这主要是因为：VGCR协议利用部分格头传输数据，并实时地切换GH模式，通过休眠，保存传感节点能量。此外，可知，随着仿真时间的推移，VGCR协议在活动节点数的优势更为明显。例如:当仿真时间为100 s时，VGCR协议的活动节点数近200，EAGER协议的活动节点数近196。而当仿真时间到达300 s时，VGCR协议的活动节点数达到195，而EAGER协议的活动节点数减少至185。

3.3 数据包传递率

两个协议的数据包传递率随信宿移动速度的变化情况，如图6(b)所示，其中数据包传递率表示信宿成功接收的数据包占总的数据包的比例。

可知，数据包传递率随信宿移动速度的增加而下降。原因在于：信宿移动越快，信宿的网格和LGH也变化越快，这增加了源节点至信宿的跳数，必然降低了数据包传递率。与EAGER协议相比，提出的VGCR协议的数据包传递率得到一定的提高。

3.4 端到端传输时延

端到端传输时延是指数据包从源节点至信实宿接收时的时间，实验数据如图6(c)所示。

图6 仿真结果

可知，端到端传输时延随信宿移动速度的增加而下降。原因在于：信宿快速移动，增加了其寻找最短路径的概率，必然降低了端到端传输时延。然而，当移动速度逐渐增加后，端到端传输时延的下降也逐渐变缓。

4 结 论

针对WSNs的节点能效问题，提出基于虚拟网格的GH连通路由VGCR。将网络划分为多个网格，并且每个网格产生一个GH，最后由GH构建数据传输的通路。而GH由活动和休眠两种状态，且可自适应地切换，进而保存了GH的能量。同时，VGCR规定只有GH参与路由，使得只有网络内的部分节点参与了路由。通过这种机制，缓解网络能耗。实验数据表明：提出的VGCR路由提高了能量利用率，延长了网络寿命。