基于NS的无线传感器网络地理信息路由协议的仿真与研究∗

赵湘宁 梁 忠

（福建农林大学计算机与信息学院 福州 350002）

基于NS的无线传感器网络地理信息路由协议的仿真与研究∗

赵湘宁 梁 忠

（福建农林大学计算机与信息学院 福州 350002）

地理信息路由协议由于其简单高效及低负载等特点，成为无线传感器网络中一类运用非常广泛的路由协议。文章利用NS2仿真平台，对GRS、GPSR和GEAR三种地理路由算法进行仿真和研究，并详细说明了在NS2中添加新路由协议的实现方法。仿真分别选取小规模节点规则分布和大规模节点随机分布的两种存在路由空洞的复杂网络环境，并选择能耗、网络生命周期、数据包到达率等算法指标，分析三种路由算法在不同网络环境中的性能。

无线传感器网络；地理信息路由；NS2仿真；路由空洞；负载均衡

1 引言

无线传感器网络（Wireless Sensor Networks，WSN）是由大量分布在监测区域内的微型传感器节点，通过无线通信的方式形成的自组织网络系统。无线传感器网络中的传感器节点收集环境中的感知数据，通过多跳方式将数据传送至汇聚节点，汇聚节点将这些数据通过互联网或者卫星传送给后台管理节点［1］。

无线传感器网络的路由协议负责将收集的数据分组从源节点转发到汇聚节点。传感器节点是一个微型的嵌入式系统，它的通信能力、处理能力和存储能力都比较有限，因此无线传感器网络的路由算法需要尽量寻找源节点和汇聚节点间的优化路由，使得路由算法的存储和计算开销比较小。此外，传感器节点通过自身携带电池供电，能量有限且不易进行能量补充，因此路由协议需要高效利用能量。

地理信息路由协议在无线传感器网络中是一类运用十分广泛的路由协议。地理信息路由算法中的节点通过GPS等方法掌握自身的地理位置信息，并通过信息交换掌握汇聚节点和一跳邻居节点的地理位置信息，并且根据这些位置信息选择路由。地理信息路由算法只需要通过局部的节点位置信息进行路由，简单高效而且负载低，已经成为无线传感器网络中重要的一类路由协议［2～8］。

本文通过网络仿真器NS2对无线传感器网络中三种经典地理信息路由协议GRS、GEAR、GPSR进行仿真，测量几种协议的网络生命周期、数据包到达率和节点能耗等性能参数。

2 相关技术

2.1 NS2

NS2（Network Simulator，Version2）是一种面向对象的网络仿真器，是一个涉及网络中物理层、数据链路层、网络路由层、能量控制、QoS等各个方面的优秀网络模拟工具［9］。目前，NS成为学术界广泛使用的一种网络模拟软件，通过NS2仿真得出的结果被学术界普遍认可。同时，NS也可以作为一种辅助教学的工具，广泛地应用在了网络技术课程的实践教学中。

NS2运行于Linux系统，是一个面向对象的、离散事件驱动的模拟器，采用两级体系结构。NS2将数据操作和网络控制部分的实现相分离，以提高代码执行效率。第一层是编译层，该层使用C++语言对大部分基本的网络组件、网络协议、事件调度器等进行编写和编译。由于网络协议的模拟和实现需要高效地处理协议的报头信息，进行大量的数据处理，因此程序内部模块的运行速度至关重要，C++快速高效的特点非常适合于这部分的工作。第二层是解释层，主要功能是对网络环境进行配置，如模拟时间、拓扑结构和节点类型。该层使用面向对象的OTcl脚本语言作为开发语言。

使用NS2进行网络模拟的基本步骤为：

1）首先，分析NS中已有的协议模块是否满足所需的仿真及研究的需求，如果满足，就可以直接编写OTcl脚本进行仿真并分析仿真结果。

2）如果NS中现有的协议模块尚不能满足需求，那么就需要对NS进行扩展，添加新的协议，或者是对已有的协议进行修改。

3）对NS完成扩展后，编写对应的OTcl脚本进行仿真，如果仿真的结果可以满足需求，则说明对NS的扩展是成功的。如果不满足，继续对NS扩展的代码进行修改，直到满足需求。

4）对仿真输出的Trace文件进行分析，得出测量网络重要性能的数据。如果需要，调整配置不同的业务量模型和网络拓扑结构，重复进行上述模拟过程，得出在不同网络环境下网络协议的性能数据。

NS模拟仿真的基本流程如图1所示。

图1 NS模拟仿真基本流程

2.2 GRS、GEAR、GPSR算法

GRS（Greedy Routing Scheme）路由［10］采用贪婪转发策略，计算当前节点的一跳邻居节点与汇聚节点的距离，选择距离汇聚节点最近的邻居作为下一跳节点。GRS算法原理简单且高效，是无线传感器网络中最经常用到的路由协议。在实际的路由过程中，GRS算法会遇到所有的邻居节点到汇聚节点的距离都比自己大的情况，这样就找不到合适的下一跳，则此时陷入了路由空洞（Routing Void）［8］，如图2中的A点。此时，GRS只能采用泛洪的方式，将数据包广播给它的所有邻居节点，如此反复，直到到达汇聚节点。泛洪方式极易产生消息的“重叠”和“内爆”［11］，造成资源的极大浪费。路由空洞现象大多发生于传感器网络中存在一些位置比较集中的失效节点，或者监测环境比较复杂的情况，比如环境中存在水塘、沼泽等不适合部署传感器节点的区域。

GEAR［12］算法将节点到汇聚节点的距离和节点的剩余能量相结合定义了路由代价，当前节点在一跳邻居节点中选择到汇聚节点路由代价最小的节点作为下一跳节点。GEAR算法计算路由代价的公式如下：

其中，c(n)为节点n到汇聚节点的代价，d(n)为节点n到汇聚节点的距离，e(n)为节点n的剩余能量，α为比例参数。

当GEAR［13］算法遭遇到路由空洞时，即当前节点的所有邻居节点到汇聚节点的路由代价都比自己的大，如图2中的A点。此时GEAR采取如下方式解决路由空洞问题：节点A选择邻居中路由代价最小的节点B作为下一跳，并将自己的路由代价值设为B的路由代价加上节点A到B的一跳通信的代价，将自己新的路由代价通知邻居节点。

GPSR算法采用贪婪转发策略作为基本的路由转发方式，当贪婪转发策略遭遇路由空洞时，就采用基于网络平面拓扑图的边缘转发方式遍历最接近的平面子图，直到来到比遭遇路由空洞的节点（即图2中的A点）更接近汇聚节点的节点时候，然后继续贪婪路由。

图2 路由空洞

2.3 在NS2中路由协议的实现

由于GRS、GEAR和GPSR协议在NS2中已有的路由协议中并没有实现，为了对这些路由协议的性能进行深入的研究，需要在NS2中实现这些路由协议。在NS2中实现新的路由协议一般需要通过添加新路由协议的代码文件、修改NS原有的一些文件、修改NS的Makefile文件这三个步骤完成。本节将通过在NS-2.35版本中实现GPSR路由协议对这三个步骤进行详细说明。

1）添加新路由协议的代码文件

一般协议的开发都是在底层C++层面完成开发的。我们在NS安装路径下的ns-allinone-2.35/ns-2.35/文件夹中新建一个文件夹gpsr，用于存放GPSR协议的代码文件，这些文件就是对协议进行描述的一些头文件和源文件。

2）修改NS原有的一些文件

由于新添加的协议需要用到NS已有的一些结构、类或者变量，所以我们需要对这些原有的信息进行更改或者扩展。例如，新的协议可能会有它自己的协议头和消息类型，那么需要对NS中定义协议头和消息类型的那些文件进行修改，添加必要的内容。不同的协议根据需要描述的内容不同，对NS进行修改的文件也不同，通常需要修改的文件有：定义消息类型和普通头部的文件packet.h以及定义分组头部的文件ns-packet.tcl。

（1）ns-2.35/common/packet.h

GPSR算法代码中使用自己的分组数据包类型PT_GPSR，我们需要修改在定义分组类型的头文件packet.h中添加GPSR定义的分组类型，有以下两处改动。

第一，找到定义分组类型的unsigned int pack⁃et_t，在这个类型中每一种分组类型都定义为一个无符号的整数，找到PT_NTYPE，这是默认在NS分组类型中的最后一个元素。我们在其前面定义一个PT_GPSR。

typedef unsigned int packet_t；

static const packet_t PT_TCP=0；

static const packet_t PT_UDP=1；

static const packet_t PT_CBR=2；

…………

…………

static const packet_t PT_GPSR=73； //GPSR

static packet_t PT_NTYPE=74；//This MUST be the LAST one

第二，在class p_info｛｝中，在相应的位置加入name_［PT_GPSR］=“gpsr”，这里添加的是在trace文件中打印PT_GPSR类型的包时需要使用的字符串。

class p_info｛

public：

p_info（）

｛

initName（）；

｝

……………………

static void initName（）

｛

……………………

name_［PT_TCP］=“tcp”；

name_［PT_UDP］=“udp”；

……………………

name_［PT_GPSR］=“gpsr”；

name_［PT_NTYPE］=“undefined”；

｝

……………………

｝

（2）ns-2.35/tcl/lib/ns-packet.tcl

GPSR协议定义了自己的分组头部，该分组头部需要在NS中被激活。我们需要修改定义分组头部的ns-packet.tcl文件，添加GPSR的分组头部。

set protolist｛

………………

GPSR #激活GPSR分组头部

………………

｝.

（3）ns-2.35/trace/cmu-trace.cc

为了使新协议的trace文件输出格式正确，还需要在cmu-trace.cc文件中加入新协议的分组数据包类型。

#include ＜packet.h＞

……………………

#include＜gpsr/gpsr_packet.h＞

……………………

void CMUTrace：：format（Packet*p，const char*why）

｛

……………………

switch（ch-＞ptype（））｛

case PT_MAC：

……………………

case PT_GPSR：

break；

default：

if（pktTrc_&&pktTrc_-＞format_unknow（p，offset，pt_，newtrace_））break；

｝

｝

（4）ns-2.35/queue/priqueue.cc

priqueue.cc中定义了数据分组队列的优先级，在其中加上新协议的分组数据包类型。

#include ＜object.h＞

……………………

void

PriQueue：：recv（Packet*p，Handler*h）

｛

struct hdr_cmn*ch=HDR_CMN（p）；

if（Prefer_Routing_Protocols）｛

switch（ch-＞ptype（））｛

case PT_DSR：

……………………

case PT_GPSR：

recvHighPriority（p，h）；

break；

……………………

else｛

Queue：：recv（p，h）；

｝

｝

3）修改NS的Makefile文件

Makefile文件位于ns-allinone-2.35/ns-2.35/下，该文件将NS2中所有协议文件整合起来进行编译和链接。在Makefile中每一个源文件需要对应一个后缀为“.o”的中间文件，这些中间文件是编译后生成的，对众多的中间文件进行链接才能生成ns命令。我们需要在Makefile文件中的OBJ_CC中增加新协议源文件的“.o”中间文件。然后保存Make⁃file，回到ns-2.35目录下，执行make命令重新编译NS。

OBJ_CC=

……………………

wpan/p802_15_4csmaca.o wpan/p802_15_4fail.o

wpan/p802_15_4hlist.o wpan/p802_15_4mac.o

wpan/p802_15_4nam.o wpan/p802_15_4phy.o

wpan/p802_15_4sscs.o wpan/p802_15_4timer.o

wpan/p802_15_4trace.o wpan/p802_15_4transac.o

apps/pbc.o

gpsr/gpsr.o

gpsr/gpsr_neighbor.o

gpsr/gpsr_sinklist.o

$（OBJ_STL）

3 实验仿真

为了全面验证与分析GRS、GEAR、GPSR这三种地理信息路由协议的性能，实验设计两种仿真场景：小规模节点规则分布的传感器网络、大规模节点随机分布的传感器网络。为了考察三种算法在复杂网络环境中的综合性能，我们在网络中设置了一些区域不布置传感器节点，以模拟真实环境中的空洞区域。

仿真采用以下3个指标来评价路由算法的性能：

1）传感器网络的生命周期：设定网络中所有传感器节点收集一次数据，并且全部传送到汇聚节点的过程即为1轮。设定网络中的死亡节点数达到全部节点的5%时，此时节点存活的轮数就是传感器网络的生命周期。

2）数据包到达率：数据包到达率测试的是数据包最终到达汇聚节点的成功率。

3）能耗：能耗指标通过当网络执行完若干次查询指令后，网络所有节点的瞬时能量损耗分布图来表示。能耗指标能够直观地反映出网络能耗的分布情况，来检验不同的路由算法在负载均衡上的性能。

3.1 小规模节点规则分布的传感器网络

我们首先采用小规模的传感器网络模型来检验三种路由算法性能。在实际应用中，一些室内环境如厂房、温室大棚等，多为小规模的传感器网络。由于网络范围不大，传感器节点可以手动地规则放置。网络中的空洞可能是由于放置一些大型的仪器设备的地方无法部署传感器节点造成的。网络模型的主要参数如下：在一个长200m、宽200m的监测区域内，规则部署了91个传感器节点。节点的无线传输半径约为30m。在监测区域范围外，部署了一个汇聚节点，汇聚节点坐标为（120.0，220.0）。图3为传感器网络节点分布图。表1为仿真中用到的参数设置。

表1 小规模传感器网络仿真中的参数设置

图3 小规模节点规则分布的传感器网络

图4 给出了无线传感器网络分别采用GRS、GEAR和GPSR路由算法，在网络生命周期性能上的比较。X轴为传感器节点的初始能量，Y轴为网络生命周期。由于网络中存在空洞，GRS采用贪婪转发策略会频繁遭遇路由空洞，并采用泛洪方式继续数据传输，故节点能量消耗很大，网络生命周期很短。GPSR算法在遭遇路由空洞时采用边缘转发方式继续数据转发，避免了采用泛洪机制，节省了节点能量消耗，延长了网络生命周期。GEAR算法结合距离和节点剩余能量计算路由代价，生成了节点能耗更加均衡的路由，所以GEAR算法的网络生命周期最长。

图5给出了随着网络查询轮数的增加，三种路由算法在数据包到达率上的比较。GPSR和GRS的数据包到达率比较接近，在执行到第250次查询时，就已经开始出现丢包的现象。在执行到600次查询时，数据包到达率约为93%。GEAR算法在执行至第400次查询时，出现丢包现象。随后数据包到达率下降很快，在600次查询时，数据包到达率约为91%。

图4 小规模传感器网络的网络生命周期的比较

图5 小规模传感器网络数据包到达率的比较

图6 给出了在节点初始能量为1.5J时，GPSR、GEAR和SIENGR算法在执行第200个查询后，网络节点的能量损耗瞬时图。在这个图中，X轴和Y轴是传感器节点的坐标，Z轴是能耗。从图6（a）中可以看出，GRS算法的节点能耗非常大，而且在200轮的时候网络中很多节点的能量消耗已经到达了1.5J。图6（b）中可以看出，GPSR算法在遇到路由空洞时，边缘转发的方式代替GRS的泛洪来继续数据转发，大幅减少了节点的能耗。但是GPSR节点的能耗分布不均衡，位于空洞边缘的节点和位于汇聚节点附近的节点能量消耗很大。从图6（c）中可以看出，GEAR算法的能耗相对于GPSR更为均横。

3.2 大规模节点随机分布的传感器网络

我们接着通过大规模节点随机分布的无线传感器网络来检验三种路由算法性能。在实际应用中，如果在监测范围较大的野外，传感器节点的布置方式多采用的是飞机空中大规模的播撒［1］，所以节点的分布状态为随机分布。网络中大规模的空洞可能为自然环境中的水塘、沼泽等。图7为仿真中的传感器网络节点分布图。传感器网络模型的主要参数如下：在一个长800m、宽800m的监测区域内，随机部署了1000个传感器节点。节点无线传输半径约为50m。监测区域内，存在着一个大小约为200*200m2的不规则空洞区域不部署传感器节点，以模拟现实环境中的真实空洞。同时，由于节点部署的随机性，在网络中间也存在着一些由于节点分布不均匀产生的小空洞，如图7中坐标（200.0，300.0）附近形成的一个小空洞区域。在监测区域范围内，部署了一个汇聚节点，汇聚节点坐标为（400.0，800.0）。表2为仿真中用到的参数设置。

图6 小规模传感器网络GRS、GPSR和GEAR的能量损耗瞬时图

图7 大规模节点随机分布的传感器网络

表2 大规模的传感器网络仿真中的参数设置

图8给出了在大规模节点随机分布的网络环境中，分别采用GRS、GPSR和GEAR路由算法在网络生命周期性能上的比较。GRS的网络生命周期最短，GEAR的网络生命周期最长。图9给出了随着网络查询轮数的增加，三种路由算法在数据包到达率上的比较。可以看出在大规模节点随机分布的网络环境中，随着节点查询轮数的增加，GRS和GPSR的数据包到达率比GEAR高一些。图10给出了GRS、GPSR和GEAR算法在执行第200个查询后，网络节点的能量损耗瞬时图。从图10（a）中可以看出，GRS在网络中出现较大空洞时频繁采用泛洪机制，导致网络能耗非常大。从图10（b）和图10（c）中可以看出GPSR和GEAR算法的能耗较之GRS有了很大的降低，但是在大空洞边缘的节点和位于汇聚节点附近的节点能量消耗较大，在网络中小空洞的周围也会出现能量消耗较为突出的小峰值。

图8 大规模传感器网络的网络生命周期的比较

图9 大规模传感器网络数据包到达率的比较

4 结语

本文针对无线传感器网络中地理信息路由进行基于NS2的仿真和研究，详细说明了在NS2中添加新路由协议的实现方法，并选取GRS、GEAR和GPSR这三种经典的地理信息路由协议进行仿真实验。仿真分别选取小规模节点规则分布和大规模节点随机分布的两种存在路由空洞的复杂网络环境，选择能耗、网络生命周期、数据包到达率等算法指标，分析三种路由算法在不同网络环境中的性能，为进一步研究无线传感器网络中的地理信息路由算法提供依据。

图10 大规模传感器网络GRS、GPSR和GEAR的能量损耗瞬时图

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京：清华大学出版社，2006.8-165.SUN Limin，LI Jianzhong，CHEN Yu，et al.Wireless Sen⁃sor Networks［M］.Beijing：Tsinghua University Press，2006.8-165

［2］Fraser Cadger，Kevin Curran，Jose Santos and Sandra Mof⁃fett.A Survey of Geographical Routing in Wireless Ad-Hoc Networks［J］.IEEE Communications Surveys and Tutorials，2012，15（2）：1-33.

［3］王建新，赵湘宁，刘辉宇.一种基于两跳邻居信息的贪婪 地 理 路 由 算 法［J］.电 子 学 报 ，2008，36（10）：1903-1909.WANG Jianxin，ZHAO Xiangning，LIU Huiyu.A Greedy Geographic Routing Algorithm based on 2-hop Neighbors［J］.Chinese Journal of Electronics，2008，36（10）：1903-1909.

［4］Tan G，Kermarrec A M.Greedy Geographic Routing in Large-Scale Sensor Networks：A Minimum Network De⁃composition Approach［J］.IEEE.ACM Transactions on Networking，2012，20（3）：864-877.

［5］Cao Y，Sun Z，Wang N，et al.Converge-and-Diverge：A Geographic Routing for Delay/Disruption-Tolerant Net⁃works Using a Delegation Replication Approach［J］.IEEE Transactions on Vehicular Technology，2013，62（5）：2339-2343.

［6］Popescu A M，Salman N，Kemp A H.Energy Efficient Geo⁃graphic Routing Robust Against Location Errors［J］.IEEE Sensors Journal，2014，14（6）：1944-1951.

［7］Boulaiche M，Bouallouche-Medjkoune L.EGGR：Ener⁃gy-aware and delivery Guarantee Geographic Routing pro⁃tocol［J］.Wireless Networks，2014：1-10.

［8］赵湘宁.一种基于信号机制的能量感知地理路由算法［J］.电子学报，2015，43（5）：788-796.ZHAO Xiangning.A Signal Mechanism Based Ener⁃gy-Aware Geographic Routing Algorithm［J］.Acta Elec⁃tronica Sinica，2015，43（5）：788-796.

［9］黄化吉，冯穗力，秦丽姣，等.NS网络模拟和协议仿真［M］.北京：人民邮电出版社，2010.1-102.HUANG Huaji，FENG Huili，QIN Lijiao，et al.NS network and protocol simulation［M］.Beijing：Posts and Telecom Press，2010.1-102.

［10］G G Finn.Routing and Addressing Problems in Large Metropolitan Scale Internetworks［R］.ISI res.repISU/RR-87-180.Mar 1987.

［11］De Couto DSJ，Robert Morris.Location proxies and inter⁃mediate node forwarding for practical geographic forward⁃ing［R］.Boston：MIT Laboratory for Computer Science，2001.

［12］Yu Y，Govindan R，Estrin D.Geographical and energy aware routing：A recursive data dissemination protocol for wireless sensor networks［R］.Technical report ucla，UCLA Computer Science Department，2001.

［13］B.Karp，H.T.Kung.GPSR：Greedy perimeter stateless routing for wireless sensor networks［C］//Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking（MobiCom_00），Bos⁃ton，2000：243-254.

Simulation and Research on Geographic Routing Protocol of Wireless Sensor Networks Based on NS2

ZHAO XiangningLIANG Zhong
（College of Computer and Information Sciences，Fujian Agriculture and Forestry University，Fuzhou 350002）

Geographic routing protocols are widely used in wireless sensor networks because of their simplicity，efficiency and low cost.This paper uses NS2 simulator platform to research three routing protocols，which are GRS，GPSR and GEAR，and presents the approach of adding new routing protocol into NS2 in details.Simulations choose two different network environments with routing voids，which are small-scale regular node distribution networks and large-scale random node distribution networks.Protocols'perfor⁃mances are evaluated by energy consumption，lifetime of sensor networks，packet delivery rate.

wireless sensor networks，geographic routing，NS2 simulation，routing void，load balancing

Class Number TP393

TP393

10.3969/j.issn.1672-9722.2017.12.025

2017年6月9日，

2017年7月20日

国家自然科学基金项目“基于X射线影像的腔内支架动力特性评价关键技术研究”（编号：61501120）；福建省教育厅科技项目“基于地理信息路由的能量空洞避免策略研究”（编号：JAT160152）资助。

赵湘宁，女，硕士，实验师，研究方向：无线传感器网络。梁忠，男，高级实验师，研究方向：算法优化、无线传感器网络。