韩小卫毕业论文（最终版本） - 图文(6)

哈尔滨工业大学工学硕士学位论文

2.2 “太子簇首-异常-竞争”单目标跟踪算法

本节详细叙述基于改进预测动态簇方法的“太子簇首-异常-竞争”跟踪算法，绪论中对预测动态簇方法已有所描述。本算法对节点进行分类，从簇首的选取机制进行改进，达到减少消息发送，节省能量的目的。

2.2.1 节点分类机制

任何一个定位时刻，当前簇首定位出目标位置后，对目标轨迹进行预测，根据预测结果对整个跟踪区域进行划分，如图2-12所示。

L0S5S3douter外区域dborderdinnerL4R1AS1S2S4S4S6L3边缘区域L2内区域L1内区域R2边缘区域外区域A：当前定位点 S1：当前簇首 S4：预定“太子簇首”

图2-12 节点分类机制

Fig. 2-12 Diagram of sensor classification mechanism

两个圆分别为目标当前的触发区域和下一时刻的预测触发区域，圆心即为当前的定位坐标和下一时刻的预测坐标。S1为当前簇首，A点为S1定位出的目标当前位置。L1为S1根据历史定位信息计算出的预测方程。过当前簇首S1作预测方程的垂线L0，将感知区域划分为两个子区域：R1和R2。在R2区域作一组平行线L2、L3、L4对R2进行细分，其到预测方程L1的距离分别为dinner ,dborder 和douter。给出区域和节点分类定义：

定义2-4 非通告候选区域：区域R1。在目标转向不超过90度的假设前提下，该区域传感器节点无需唤醒。

定义2-5 通告候选区域：区域R2。在目标转向不超过90度的假设前提下，被唤醒传感器节点位于该区域。进一步，该区域又被分为三个区域：

定义2-6 内区域：Rinner。Rinner?{p|dis(p,L1)?dinner- 21 -

p?R2}，dis(p,L)

哈尔滨工业大学工学硕士学位论文

表示点p到直线L的距离（下同）。

定义2-7 边缘区域：Rborder。Rborder?{p|dis(p,L1)?(dinner,dborder]p?R2}。 定义2-8 外区域：Router。Router?{p|dis(p,L1)?(dborder,douter]p?R2}。

如图2-12所示，L1，L2之间区域属于内区域Rinner，L2，L3之间区域属于边缘区域Rborder，L3，L4之间区域属于外区域Router。

定义2-9 节点类别：内区域内的节点为内节点，边缘区域内的节点称为边缘节点，外区域内节点称为外节点。

节点类型的确定紧密依赖于三个相关值：dinner ,dborder 和douter。其大小根据不同感知模型节点的属性动态调整，获得最优值。本文中的声音传感器节点，其感知模型：

ifRdetect?r?dis(Si,T)?0,?????P(Si)??e,ifr?Rdetect?dis(Si,T) (2-12)

?1,ifRdetect?r?dis(Si,T)?其中，dis(Si, T)表示目标点T (x, y)到传感器Si的距离；α= dis(Si, T)- (Rdetect-r)，

β和λ为经验常数，Rdetect为节点感知半径，r是一个与节点自身相关的值。则P(Si)表示节点Si发现位于该点目标的概率公式[18]。因此，根据该公式，可以选取dinner = Rdetect – r, dborder = Rdetect, douter = Rdetect + r。使得从内区域到外区域，节点发现目标的概率从大到小。具体地，内节点发现目标概率为1，外节点发现目标概

?率为0，边缘节点为e???。

2.2.2 “太子簇首-异常-竞争”算法

2.2.2.1 算法描述

定义2-10 太子簇首：由当前簇首确定的预测方向上有可能成为下一定位时刻簇首的节点。

算法的基本思想：从新簇首的产生以及新簇的确立过程考虑，突破CH一般情况下采用 “选举”或“竞争”的思想，而是采取“太子簇首”的方法。即当前CH根据预测方向上的邻居节点分布以及节点分类情况，选取最适合的节点预订为下一定位时刻的簇首。从而避免“选举”或“竞争”带来的通信负载和无线信号冲突，节省能耗且提高跟踪效率。对于预测误差过大或目标偏离带来的“太子簇首”选取失败的情况，则采取传统的“竞争”方法。

算法要解决几个主要问题是“太子簇首”选取、唤醒通告和新簇的形成。 (1) 太子簇首的选取

- 22 -

哈尔滨工业大学工学硕士学位论文

太子簇首由当前簇首确定。选取的方法有多种，主要依据跟踪精度和目标运动速度。例如，在当前簇首可直接通信的范围内，选取距离最远的那个内节点为太子簇首节点，如图2-12中节点S4。这样可以减少定位点，从而降低整体能耗，但可能带来定位点密度的减小，从而有一定的跟踪精度损失。选取距离较近的节点如S2可以提高定位密度和跟踪精度，又增加了能量消耗。因此，实际中，应在满足跟踪精度要求的情况下选取距离尽可能远的节点。此外，还需考虑目标运行速度。若目标速度很快，而选取距离又相对过小，则会造成目标的丢失。此时需要选取远距离的节点作为“太子簇首”，但该节点有可能超出当前簇首的无线通讯距离，因此需要多跳通讯[28]。

(2) 唤醒通告

簇首完成预测、节点分类、“太子簇首”选取的工作后，即开始唤醒预测方向上的睡眠节点，使其进入工作状态。具体地，发送唤醒消息AwakeMsg到通告候选区域。消息AwakeMsg封装了节点分类以及太子簇首选取的结果。睡眠节点收到AwakeMsg消息后，开始监听，且知道自身的节点类型以及是否是太子簇首。

(3) 新簇的形成

为了保证对移动目标的持续跟踪，在目标即将离开当前簇感知范围时要及时形成新簇，以便由新簇接续负责对目标的跟踪。新簇的形成主要有三种情形： ? 太子簇首“晋升”为正式簇首并形成新簇

如果预测方程足够准确，且能够找到符合要求的节点作为太子簇首。则该太子簇首收到触发时，开始定位：发送定位查询消息LocateMsg到周边节点。收到此定位查询信号的周边节点如果处于发现目标状态，即发送回复消息ReplyMsg到簇首，内含该节点对目标的量测。簇首即根据收到的ReplyMsg提供的信息和自身量测信息完成对目标的定位。若定位成功，太子簇首正式成为簇首。首先向上一簇首发送“承接”信号，表示新簇已经建立，目标没有丢失，上一簇首收到该信号，放弃簇首地位。然后该新簇首进入新的预测、节点分类、太子簇首选取、唤醒通告的新一轮循环。该过程称为太子簇首跟踪模式。若定位失败，则广播定位失败信号FailMsg。FailMsg消息通知其他节点当前太子簇首定位失败，开始进入“竞争”跟踪模式。

? “异常”节点成为簇首并形成新簇

定义2-11 异常：目标实际轨迹与预测轨迹发生较大误差，使得外节点受到目标触发，这种情况称为异常。受到触发的外节点称为异常节点。对应的定位称为异常定位。该跟踪模式称为异常跟踪模式。

- 23 -

哈尔滨工业大学工学硕士学位论文

根据节点分类，在预测足够准确且目标运动方向不发生大的偏转情况下，外节点不会受到目标触发。因此，若是普通内节点（非太子簇首）和边缘节点受到触发，则只是简单标志节点为发现目标状态，然后继续监听，并等待接受太子簇首的定位查询信号。若是外节点受到触发，则立即“篡位”成为异常节点。广播发送异常定位查询消息ExceptionMsg，其他节点收到ExceptionMsg后，回复ReplyMsg到该异常节点。原来的太子簇首收到ExceptionMsg后，放弃太子簇首地位，成为普通节点。异常节点根据收到的ReplyMsg及自身量测进行异常定位。若定位失败发送FailMsg进入竞争跟踪模式。

? 普通节点通过“竞争”成为簇首并形成新簇 上述两种情形下，在定位失败时开始进入竞争跟踪模式。所有节点通过“竞争”形成新的簇首。任何节点受到触发，即发送定位查询信号LocateMsg进行定位查询，定位成功则晋升为簇首[28]。

定理2-1 上述三种跟踪模式不会同时发生，即不会相互冲突。

证明：首先，太子簇首跟踪和竞争跟踪是互斥的。在太子簇首定位失败的情况下，才会采取“竞争”的方式生成下一个簇和相应的簇首，而该新簇若定位成功，又会采取“预测-节点分类-太子簇首选取-唤醒通告”一系列步骤“回归”到太子簇首跟踪模式。其次，竞争跟踪和异常跟踪是互斥的。同太子簇首跟踪，异常跟踪在定位失败的情况下才会开始竞争跟踪模式。最后，异常定位和太子簇首定位也是互斥的。显然，该“异常”本身就是相对于太子簇首的“正常”情况而言的，在收到异常定位查询消息ExceptionMsg后，原来的太子簇首节点立即放弃其“地位”，成为普通节点，所以不会与异常定位跟踪相冲突。因此，三种跟踪模式两两互斥，不会同时发生。 2.2.2.2 算法设计与分析

根据上述算法描述，给出该算法流程：

算法2-1. “Prince-Exception-Competition” algorithm running at each sensor 算法输入：触发/无线信号，算法输出：定位结果/无线信号 1: while(节点在工作){

2： event1 ：受到触发 3: switch(节点类型)

4: { case ?太子簇首?：

5: send(LocateMsg); //发送定位查询消息LocateMsg; 6: receive(ReplyMsg); //接收回复消息ReplyMsg 7: locate(); //定位

- 24 -

哈尔滨工业大学工学硕士学位论文

8: if(定位成功)

9: { 成为正式簇首；

10: 预测目标未来状态； 11: 节点分类；

12: 选取下一太子簇首；

13: send(AwakeMsg); //发送唤醒通告消息AwakeMsg 14: }else //定位失败

15: send(FailMsg); //发送定位失败消息FailMsg 16: break;

17: case ?外节点?：

18: send(ExceptionMsg); //发送异常定位查询消息 19: goto 6; //回到第6行 20: case ?边缘节点或普通内节点?：

21: detected = true; //detected标志是否发现目标22: }

23: event2：收到消息

24: switch(消息类别)

25: { case ?AwakeMsg?： //通告唤醒消息

26: 根据AwakeMsg消息初始化自身类型，开始监听。 27: break;

28: case ?LocateMsg?： //定位查询消息

29: if( detected == true) //如果该节点发现目标 30: send(ReplyMsg); //发送回复消息Reply 31: break;

32: case ?ExceptionMsg?： //异常定位查询消息

33: if( 该节点为太子簇首) 放弃太子簇首地位； 34: goto 29;

35: case ?FailMsg?： //定位失败消息 36: 开始竞争簇首； 37: } 38: }

接下来，通过与另外两种方法的对比分析，来说明本算法的低能耗特点。假设定位方法采用三角形质心定位，网络需满足三度覆盖，每个簇首须收到至

- 25 -

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库韩小卫毕业论文（最终版本） - 图文(6)在线全文阅读。