省基金申请书参考 WSN中基于区域划分的半自动DV-Hop定位算法 陈庆章

省基金申请书草稿（原创、未使用）

陈庆章

1．项目名称

基于区域划分的半自动DV-Hop定位算法的研究及其应用

2．研究工作的科学意义

随着传感器技术、嵌入式技术、分布式信息处理技术和无线通讯技术的发展，以大量的具有微处理能力的微型传感器节点组成的无线传感器网络（Wireless Sensor Network，WSN）逐渐成为学术界的研究热点，也成为工业界拓展应用的热点。无线传感器网络是众多的传感器节点通过无线通信的方式相互联系，传递和处理信息的网络，可以实时检测、感知和采集网络分布区域内的各种环境或监测对象的信息，通过无线网络最终传递给观察者，它是集数据采集、数据处理、数据传输于一体的复杂系统，在军事、环境、生物、医疗保健、空间探索和商业应用方面显示了极大的应用价值[1]。

在WSN领域中有很多亟待解决与研究的关键问题，节点定位问题就是其中之一。节点定位指的是无线传感器网络中的传感节点，根据少数已知位置的节点，通过执行某种方法或运行某个算法获取到自身在网络中的物理位置。根据节点是否已知自身位置，节点可分为信标节点（Anchor）和未知节点。信标节点通过携带GPS定位设备或手动写入等手段获得自身的精确位置，在网络节点中占的比例很小；其它非信标的节点就是未知节点，它们通过信标节点来确定自身位置[2]。

目前已有众多的WSN节点定位算法被提出，根据定位过程是否实际测量节点间距离，这些定位算法大体分为两类：基于距离（Rang-based）的定位和距离无关（Rang-free）的定位。基于距离的定位机制，是通过实际测量相邻节点间的距离或方位来计算未知节点的位置，通常有测距、定位和修正等几个步骤[7]，常用的测距方法包括TOA （Time of Arrival，到达时间）、TDOA（Time Difference of Arrival，到达时间差）、AOA（Angle of Arrival，到达角度）、RSSI（Received Signal Strength Indicator，接受信号强度指示）等[3]；距离无关的定位机制，无需测量实际距离，而是根据网络连通性等信息实现距离估计或确定包含未知节点的可能区域，来确定未知节点的位置[2]。距离无关定位算法在成本和功耗方面有较大优势，所以是目前研究的热点。已经提出的距离无关定位算法主要有APIT算法[4]、质心算法[5]、DV-Hop算法[6]等，这其中影响最大，应用最广泛的当属DV-Hop算法。

节点的自我定位对于无线传感器网络应用有着重要意义，这是由WSN应用的一些特点所决定的：

1)、节点分布空间广，位置随机性极大

比如在军事应用方面，在战场上部署无线传感器网络跟踪敌人的军事行动，传感器节点可以大量地装在宣传品、子弹或炮弹壳中，在目标地点撒落下去，形成大面积的监视网络[8]。这就使得每个节点在网络中的物理位置具有极大的随机性，不可能在布网的时候手动指定每一个节点的位置。

2)、无线传感器网络收集的信息具有很大的位置依赖性

在很多无线传感器网络中，位置信息对传感网络的监测活动至关重要，事件发生的位置或获取信息的节点位置是传感节点监测消息中所必须包含的重要信息，没有位置信息的监测消息往往是毫无意义的[9]。比如将无线传感器网络应用于火灾、地震等灾难的监测，如果监测消息中没有灾难发生的位置信息，则这些消息没有任何参考价值。考虑到为每个节点手动指定位置是不现实的，这就要求无线传感器网络节点具有自我定位的能力。

3．本项目研究目标，及其与申请者研究工作长期目标的关系

研究目标：

本项目将设计并实现一个“基于无线传感网络的室内紧急逃生引导系统（IEEGS）”，它是一个构建在无线传感器网络上，执行灾难监测和逃生引导的系统，它对网络中节点的位置信息有很大的依赖。本项目将为该系统设计一个符合其特定需求的定位方法，具体的研究目标有以下几个方面：

1．解决IEEGS的节点定位问题，使得系统中的无线传感器节点能够实现自我定位。

2．IEEGS系统中的节点能够以较高的精度获取自身位置坐标。

3．利用IEEGS系统网络拓扑所具有的一些特性，提升所用定位方法的性能，以使得其更适合应用在IEEGS系统中。

与申请者研究工作长期目标关系：

我们近年来一直在物联网领域开展大量的研究工作，承担了多项省内重大项目。本项目研究工作的展开，是以往工作经验的发挥和应用，有助于提高WSN中节点的自我定位能力及精准度。今后我们还将持续关注基于WSN的各类系统在不同环境下对节点定位能力的要求，不断进行改进，确保其适应各种环境，这也是我们实验室的长期目标。

4．项目研究内容、研究方案和进度安排

项目研究内容：

1)、在DV-Hop算法的基础上，提出一种“基于区域划分的半自动DV-Hop”定位算法，该算法的核心思想是：半自动平均每跳距离获取、区域划分和坐标贴边。通过在算法中应用这些思想，改进DV-Hop存在的不足，使得改进后的DV-Hop算法适应IEEGS需求，从而形成了一个满足IEEGS特定的定位要求和性能较高的定位算法。

4．对本文提出的算法进行了仿真验证，在理论上验证其有效性，评估其性能表现。

5．对本文的定位算法进行了实验验证，在实际的IEEGS系统中验证算法的有效性，评价其实际运行性能。

项目研究方案及技术路线：

基于区域划分的半自动DV-Hop (ADBSA DV-Hop)算法基于DV-Hop，根据IEEGS系统的特殊定位需求改进而来。和DV-Hop算法相同，其核心思想也是把两节点间的距离表示为它们之间跳数与网络平均每跳距离的乘积，在此基础上，ADBSA DV-Hop融合了半自动平均每跳距离获取、区域划分、坐标贴边的思想，以适应IEEGS的定位需要，提高算法的实际应用性能。

ADBSA DV-Hop分为两部分执行，第一部分为算法参数配置，第二部分为算法实际运行。

算法参数配置部分。在ADBSA DV-Hop运行中需要使用到的参数，必须事先向每一个节点中写入，这些参数包括：

1)、节点所处区域坐标：根据网络的总拓扑图，对目标网络进行矩形区域划分以后，需要对每一个节点进行设置，以使其了解自身所处区域。区域坐标参数为),(),(2211yxyx的形式，其中),(11yx是区域左上顶点坐标，),(22yx是区域右下顶点坐标。

2)、区域节点密度与节点通信半径r：在网络不同的区域中，节点密度和节点通信半径都不尽相同，为了使用半自动方式获取平均每跳距离，需要在节点中写入其所在区域的节点密度和节点通信半径。

3)、修正因子m：半自动获取网络平均每跳距离时，为了使计算环境贴近实际情况，需要使用修正因子m对计算结果适当调整。

4)、贴边门限值k：经过定位算法，节点首次获得自身位置坐标后，会根据这个坐标与区域边缘的距离远近，决定是否进行坐标贴边。在判断与区域边缘距离关系的时候，需要用到贴边门限值k，这个值也必须被事先写入节点。关于k值的选取策略将在下文中提到。

5)、信标节点坐标：ADBSA DV-Hop的定位过程依赖于信标节点位置坐标。信标节点坐标可以事先人工写入，也可以给信标节点携带GPS等设备运行时获取。

算法实际运行部分。正式进入ADBSA DV-Hop算法流程，开始定位过程。与DV-Hop算法相似，ADBSA DV-Hop定位过程由4个互不重叠的阶段组成：

第1阶段，未知节点计算与信标节点的最小跳数。使用典型的距离矢量交换协议，通过节点间的信息交换，使网络中所有节点获得与信标节点之间的跳距。具体过程为：所有信标节点向邻居节点广播自身位置信息分组，分组格式如下：

ID Hop X Y X1 Y1 X2 Y2

其中ID是每个信标节点的唯一标识；Hop是到这个信标节点的跳数，跳数字段值被发出该分组的信标节点初始化为1；(X,Y)是信标节点坐标；(X1, Y1)- (X2,

Y2)是信标节点所在区域。接收到分组的节点首先根据(X1, Y1)- (X2, Y2)判断该信标节点是否属于本节点所在区域，如果不是，则丢弃这个分组，否则记录下到这个信标节点的最小跳数，忽略来自同一信标节点的跳数值较大的分组，然后将分组中的Hop字段值加1，并转发给邻居节点，最终使得网络中的所有节点都能够记录下到自身所在区域内每一个信标节点的最小跳数。

第2阶段，计算未知节点与信标节点的跳数距离。未知节点收到与信标节点的跳数信息后，就可以利用下式计算到这些信标节点的几何距离：

iihopASPHd

id是节点到信标节点i的距离，ASPH是网络平均每跳距离，ihop为节点到信标节点i的跳数。

第3阶段，计算节点坐标初值。当一个未知节点获得与3个或更多信标节点间的跳距之后，使用三边测量法计算自身位置，获得其位置坐标的初始值。

第4阶段，坐标贴边。完成第3阶段的未知节点，根据自身坐标初值、所处区域的坐标、贴边门限值k，执行坐标贴边过程。贴边完成后获得节点坐标校正值，并作为节点的最终位置坐标。

在ADBSA DV-Hop定位过程中，除了完成基本的算法流程以外，可以引入一些优化策略，以提高算法的性能。 1)、自动获取平均每跳距离与半自动获取结合

上文中提出的半自动平均每跳距离的获取方法是为了解决DV-Hop算法中ASPH值获取不稳定的问题，然而这种半自动的获取方法存在一定程度的主观性，且太过理论化，在实际应用过程中可能反而会影响定位精度。

出于对这个问题考虑，可以将自动获取平均每跳距离和半自动获取两种手段结合起来使用，在算法的第2阶段，首先按照原DV-Hop算法的自动方式，由信标节点计算ASPH，并向就近的的未知节点分发；收到ASPH的未知节点，使用本文的半自动方式计算ASPH’，取二者的平均值；无法收到ASPH的未知节点，只使用半自动方式获取平均每跳距离值。

2)、多信标组合重复计算

当一个未知节点确定了与3个信标节点的距离时，就可以使用三边测量法计算自身位置，然而仅仅根据3个信标节点所计算出来的坐标往往精度较低。在一般情况下，网络中的大部分未知节点都可以获取到与3个以上信标节点的距离，此时可以选择多个信标节点组合重复计算，取结果的平均值，以提高计算精度。

理论上，当一个未知节点得到与n个信标节点间距离时，它可以使用3nC种信标组合来计算自身坐标。 N4(X1,Y1)N3N1NN2(X,Y)(X2,Y2)(X3,Y3)(X4,Y4)

图1 多信标组合重复计算

如图1所示，节点N获得了与4个信标节点的距离，可以使用434C种信标组合计算，得到4个坐标分别为(X1,Y1)、(X2,Y2)、(X3,Y3)、(X4,Y4)，计算由这4点围成的多边形的质心（取平均值），作为节点N的坐标：

)44321,44321(),(YYYYXXXXYX

3)、提升非信标节点为信标节点

在网络中可能会存在有一部分节点，这些节点在它们的可通信范围内无法与3个以上信标节点取得联系，从而无法计算出自身准确的位置，这样的节点称为不良节点。如图2所示，在(a)中不良节点N只能连接到一个信标节点1，在使用三边测量法计算位置时只能列出一个方程，它的解是一个圆周，即无法得到节点N的准确位置，它可能在以节点1为圆心，N和1之间距离为半径的圆周上的任何一个位置；在(b)中不良节点N能连接到两个信标节点1、2，可以列出两个方程计算，解有两个值，处在以1、2连线为对称轴的两个相对位置上，同样无法确定N的准确坐标。