一种无线传感器网络中基于传送树的目标跟踪方法

摘要

本发明公开了一种无线传感器网络中基于传送树的目标跟踪方法，当目标足够接近覆盖区域的边界时，执行节点加入算法形成初始树，靠近目标的其中一个节点被选为临时根；每个感知到目标的节点使用模糊推理规则来找到它与目标的模糊距离；从“非常远”区域进入到“远”区域的节点执行节点加入算法，然后传送树进行重新配置；为了使根尽可能接近目标，算法从“非常近”区域选择一个节点作为永久根；当临时根远离目标和改变区域时将广播其状态；声明为新的临时根时广播此信息，每个现有节点更新其数据库，旧的临时根将新的根设置为其父节点。本发明的传送树是在覆盖区域内目标的周围建立的，可以实现100％的覆盖，提高了获取信息的准确性。

说明书

技术领域

本发明属于无线传感网络领域，涉及一种无线传感器网络中基于传送树的目标跟踪方法。

背景技术

无线传感器网络(Wireless Sensor Networks,WSNs)是由部署在覆盖区域内的大量廉价微型传感器节点组成，这些节点具有通信能力和计算能力，通过多跳无线通信的方式构成自组织网络系统，对覆盖区域内的环境或监测对象的信息实时感知、采集和处理，并将处理后的信息传送到感兴趣的网络终端用户。作为一个新兴的热点领域，无线传感器网络以其先进的理念和广泛的应用前景日益受到全球学术界与工业界的高度关注，被看作是继因特网之后将对21世纪人类生活方式产生重大影响的IT技术之一，其广阔的应用前景引起了全世界范围的广泛关注，由此衍生的很多技术问题也成为国内外研究的热点。

WSNs非常重要的应用领域是监视、栖息地检测等，在覆盖区域内部署网络来跟踪目标的移动。跟踪目标的方法之一是使用传送树。感知到目标的节点相互协作在目标周围形成一个有根的树形结构。随着目标的移动树形结构将进行重新配置。这个树形结构在覆盖区域内总是随着目标移动，因此被称为传送树。当目标移动时新的节点加入树中而一些旧的节点离开树。树中的任何节点不会将收集的数据直接发送到基站，而是发送到根节点。因为树中的所有节点都在感知同一个目标，在收集到的数据过程中有大量的数据冗余。

目前，基于传送树的目标跟踪算法中，很少可以实现100％的树覆盖率，并且随着传送树的移动，不断有节点加入和移出，传送树需要不断进行构建和重新配置，使得无线传感器网络的能量损耗增大，导致整个网络的寿命减小。

发明内容

本发明针对现有技术中存在的上述问题，提出了一种无线传感器网络中基于动态传送树的移动目标跟踪方法，利用一种模糊感知模型实现了传送树的扩张、删减以及树的重新配置，具有100％的树覆盖率和低能耗。

为实现上述目的，本发明的技术方案为一种无线传感器网络中基于传送树的目标跟踪方法，包含以下步骤：

1)当目标足够接近覆盖区域的边界时，沿着边界或靠近边界的一些节点开始监测到目标，这些节点执行节点加入算法形成初始树，靠近目标的其中一个节点被选为临时根；

2)每个感知到目标的节点使用模糊推理规则来找到它与目标的模糊距离，无线传感器网络内的每个节点都必须属于其中某一个模糊区域，具体取决于它们与目标的模糊距离，如果任何节点超出目标的范围，则该节点属于“非常远”区域；

3)从“非常远”区域进入“远”区域的节点执行节点加入算法，类似地，从“远”区域移动到“非常远”区域的节点将成为需要从树中删除的候选节点，并且执行节点删减算法，只要这些节点改变它们的模糊区域，传送树就要进行重新配置；

4)为了使根尽可能接近目标，算法从“非常近”区域选择一个节点作为永久根，如果在“非常近”区域中存在多于一个节点，则具有最高等级的节点将被选择为永久根，如果“非常近”区域中不存在节点，则来自最近区域的节点将被选择为临时根；

5)当临时根远离目标并改变区域时将广播其状态；

6)当树中的节点向目标移动并改变模糊区域时，检查其模糊距离是否优于临时根，如果是，则将其声明为新的临时根并广播此信息，收到此广播，每个现有节点更新其数据库，旧的临时根将新的根设置为其父节点。

进一步，上述节点加入算法包含如下步骤：

1)把从“非常远”区域移动到“远”区域的节点作为加入传送树的候选节点，这些节点首先广播包含其ID和等级的节点加入消息，以找到其父节点并等待t₁时间；

2)当树节点接收到节点加入消息时，立即向发送者发送节点接受消息，如果树存在，那么加入节点接收到至少一个来自树节点的节点接受消息，将此消息的第一发送者作为其父节点，并向父节点发送一个包含其ID的子节点消息，在接收到子节点消息时，树节点将发送者保存为其一个子节点；

3)如果传送树不存在，加入节点n_i在t₁时间内接收到J-1个节点加入消息，将在那些消息中其他节点的等级与自身等级进行比较，在以下两种情况下将自身选为临时根：i)如果节点n_i具有最大的等级；ii)如果节点在等级相同时具有最小ID，否则，设置具有最大等级或最小ID的其他节点作为其父节点以及树的临时根；

4)如果加入节点n_i在t₁时间内没有接收到任何消息，即树不存在并且只有一个加入节点，则选择自身作为临时根并开始形成树。

上述节点删除算法包含如下步骤：

1)当目标移动时，把从“远”区域移动到“非常远”区域的节点从传送树中移出，如果树节点的剩余电池电量下降到临界值以下，则将它从传送树中移除，从传送树离开的节点将包含其所有子节点ID的节点离开消息发送到其父节点，并将包含其父节点ID的新父节点消息发送到其所有子节点；

2)父节点在接收到节点离开消息时，从其子节点列表中删除相应的节点；

3)当节点从其父节点接收到新父节点消息时，将父节点替换为由消息中父节点ID标识的新父节点；

4)当临时根节点本身从“远”区域移动到“非常远”区域或其剩余电池电量可能下降到临界值以下，临时根发送子根消息给它的所有子节点；

5)接收到子根消息的节点开始新临时根的选举，每个这样的节点广播包含其ID和等级的节点数据消息，然后等待t₄时间，在该时间内，节点n_i可以接收到D个节点数据消息，然后，节点n_i将其等级与在这D个节点数据消息中其他节点的等级进行比较，如果节点n_i发现其等级是最大或者跟其他节点的等级同为最大但其ID最小，它就声明自己是新的临时根，并广播一个根选举消息来通告这个选举，否则，节点n_i将等级最大的其他节点设置为新根以及其父节点。

上述根节点选择算法包含如下步骤：

1)从“非常近”区域的节点中选择永久根，当永久根刚离开“非常近”区域或者其电池能量下降到临界水平以下时，永久根选举程序被触发，准备离开的根广播包含根ID、根类型和根区域的根离开消息；

2)如果树中没有节点，则准备离开的根将不会接收任何消息，并且它将继续作为临时根；

3)如果有节点存在于“非常近”区域中，则向发送者回送节点接受消息，从而使得根接收到N个节点接受消息并将第一发送者设置为其父节点；

4)“非常近”域中的节点在接收到根离开消息之后开始新根的选举，广播包含节点ID及其等级的节点数据消息，接收D个节点数据消息后，“非常近”区域中的每个节点n_i从消息中找到等级最大的节点，并与其自己的等级进行比较，如果节点n_i的自身等级大于n_max的，则自身作为新的永久根并广播根改变的消息，如果等级相同，若节点n_i的ID最小，则还选择自身作为新的永久根，否则，选最大等级的节点作为新的根和父节点。

上述临时节点算法包含如下步骤：

1)当临时根远离目标并更改其模糊区域时，广播包含根的ID、类型和当前区域的根区域更改消息；

2)任何节点接收到该消息，比较自身区域是否比所广播的更好，如果是，则节点向临时根发送包含其ID和等级的根更改消息；

3)在t₂时间后，临时根可以接收“C”个这样的消息，在这“C”个消息中，临时根找到具有最大等级的节点，如果等级同为最大的则找到具有最小ID的节点，选择该节点作为新的临时根，并广播包含新临时根的ID、区域和类型的根更改消息，并将新根设置为其父节点；

4)任何树节点接收到根改变的消息后，更新根信息，新的根节点将其状态更改为临时根。

上述“非常近”区域节点算法包含如下步骤：

1)当树节点n_i从N区域进入VN区域时，它检查现有根的类型，如果现有根是永久性根，则将根设置为其父节点，并将包含其ID的根加入消息发送到根节点，当永久根接收到根加入消息时，将发送者设置为其一个子节点，另一方面，如果根是临时的，则节点n_i将自身设置为新永久根，并广播包含自身ID、根类型及其区域的根改变消息；

2)当旧的临时根接收到这种根改变消息时，将发送节点设置为其父节点并更新根信息；

3)除了节点n_i的所有树节点以及旧根在接收到根改变消息时，用消息中的根信息更新其数据库。

本发明还进一步提出一种上述无线传感器网络中基于传送树的目标跟踪方法中使用的无线传感器网络的系统模型，假设无线传感器网络由统一部署在一个区域内的n个传感器节点组成，设传感节点为n_i，相关的传感节点序列为V＝{n₁,n₂,…,n_i,…,n_N}，其中|V|＝N，传感器节点和底层网络模型如下：

1)传感器随机地部署在一定的区域上；

2)在远离方形传感区域的地方有一个基站，即数据接收端；

3)传感器和基站在部署之后都是固定的；

4)所有节点是同构的并且具有相同的功能；

5)每个节点被分配唯一的标识符；

6)节点可以根据需要通过改变传输功率来改变它们的传输范围，即节点具有可变的通信半径；

7)假定任何节点可达到的最大通信范围r_c大于监测范围r_s；

8)节点使用GPS设备或运行某种算法以获得它们的精确位置信息；

9)节点可以使用功率控制来改变传输功率，其值取决于到接收端的距离；

10)链路是对称的，节点可以使用相应的模糊推理系统，根据接收的信号强度来计算到另一个节点以及汇聚节点的近似距离。

进一步，作为优选，r_c≤2r_s。

与现有技术相比，本发明的优点和有益效果：

1)本发明的算法在目标靠近覆盖区域并且还不在覆盖区域内时就开始跟踪并捕捉。这样保证了目标刚开始的时候就能够被检测到。

2)本发明的传送树是在覆盖区域内目标的周围建立的。在目标范围内的传感器节点被包含在传送树内，实现了100％的覆盖，提高了获取信息的准确性。

3)本发明使用了成熟的模糊区域模型，传送树重新配置的情况变少。使用模糊区域概念使得节点的加入和删减限于局部，从而减少了用于树的构建和重新配置的能量损耗。

4)本发明中每个父节点使用数据聚合和压缩技术来减少要传送的数据量，并且提高了信息的质量，使得根节点从树中接收到非常简洁的信息。从而使数据传输的能量损耗在很大程度上减少。

附图说明

图1为本发明所述的基于动态传送树的目标跟踪方法中的节点加入算法具体流程；

图2为节点删除算法具体流程；

图3为根节点选择算法具体流程；

图4为临时节点算法具体流程；

图5为VN区域的节点具体流程。

具体实施方式

现结合附图对本发明做进一步详细的说明。本发明首先提出了一个无线传感器网络的系统模型。假设无线传感器网络由统一部署在一个区域内的n个传感器节点组成，设传感节点为n_i，相关的传感节点序列为V＝{n₁,n₂,…,n_i,…,n_N}，其中|V|＝N。传感器节点和底层网络模型如下：

1)传感器随机的部署在一定的区域上；

2)在远离方形传感区域的地方有一个基站(即数据接收端)；

3)传感器和基站在部署之后都是固定的；

4)所有节点是同构的并且具有相同的功能；

5)每个节点被分配唯一的标识符(ID)；

6)节点可以根据需要通过改变传输功率来改变它们的传输范围，即节点具有可变的通信半径；

7)假定任何节点可达到的最大通信范围(r_c)大于监测范围(r_s)。更具体地，r_c≤2r_s；

8)节点使用GPS设备或运行某种算法以获得它们的精确位置信息；

9)节点可以使用功率控制来改变传输功率，其值取决于到接收端的距离；

10)链路是对称的，节点可以使用相应的模糊推理系统，根据接收的信号强度来计算到另一个节点以及汇聚节点的近似距离。

为了减少传送树重新配置的能量损耗，本发明提出了一种成熟的模糊感知模型。根据目标发射的信号强度在目标周围形成五个模糊区域。这些模糊区域是：

1)VN(very near)区域，非常接近、目标信号非常强的区域；

2)N(near)区域，接近目标、信号强的区域；

3)M(moderate)区域，与目标中等距离、信号中等强度的区域；

4)F(far)区域，距离目标远、信号弱的区域；

5)VF(very far)区域，距离目标非常远、信号非常弱的区域，位于该区域传感器节点不能再监测到目标。

本发明在模糊感知模型的基础上提出了一种无线传感器网络中的目标跟踪方法。该方法首先规定了传送树节点的三个操作：1)连接进入目标范围内的新节点(可以微弱地监测到目标)，2)删除已超出目标的范围(不能监测到目标)的节点，3)调整现有节点，重新配置树，使树根保持尽可能接近目标。

本发明所述实现目标跟踪的动态传送树的形成步骤如下：

1)当目标足够接近覆盖区域的边界时，沿着边界或靠近边界的一些节点开始监测到目标。这些节点执行节点加入算法形成初始树。靠近目标的其中一个节点被选为临时根。

2)每个感知到目标的节点使用模糊推理规则来找到它与目标的模糊距离。无线传感器网络内的每个节点都必须属于其中某一个模糊区域，具体取决于它们与目标的模糊距离。如果任何节点超出目标的范围，则该节点属于“非常远”区域。

3)从“非常远”(VF)区域进入“远”(F)区域(刚进入目标的监测范围)的节点执行的节点加入算法。类似地，从“远”(F)区域移动到“非常远”(VF)区域(距离刚好不能监测目标)的节点将成为需要从树中删除的候选节点，并且执行节点删减算法。只要这些节点改变它们的模糊区域，传送树就要进行重新配置。

4)为了使根尽可能接近目标，算法从VN区域选择一个节点作为根(永久)。如果在VN区域中存在多于一个节点，则具有最高等级的节点将被选择为永久根。如果VN区域中不存在节点，则来自最近区域的节点将被选择为根(临时)。

5)当临时根远离目标和改变区域时将广播其状态(临时或永久，其模糊距离等)。

6)当树中的节点向目标移动并改变模糊区域时，检查其模糊距离是否优于临时根。如果是，则将其声明为新的临时根并广播此信息。收到此广播，每个现有节点更新其数据库，旧的临时根将新的根设置为其父节点。

本发明所述的基于动态传送树的目标跟踪方法采用了节点模糊等级划分。覆盖区域内的每个节点定期地通过表1中定义的模糊推理规则来计算其等级。等级计算取决于电池剩余能量。在计算等级时，节点读取电池状态，设置电池剩余能量，并使用规则找到对应的等级。

表1节点电池剩余能量及其对应的等级

电池剩余能量等级零零少低中等中多高很多很高满最高

本发明所述的传送树的节点加入算法如图1所示，具体步骤如下：

1)把从VF区域移动到F区域的节点作为加入传送树的候选节点。这些节点首先广播包含其ID和等级的节点加入消息以找到其父节点并等待t₁时间。

2)当树节点接收到节点加入消息时，立即向发送者发送节点接受消息。如果树存在，那么加入节点接收到至少一个来自树节点的节点接受消息，将此消息的第一发送者作为其父节点并向父节点发送一个包含其ID的子节点消息。在接收到子节点消息时，树节点将发送者保存为其一个子节点。

3)如果传送树不存在，加入节点n_i在t₁时间内接收到J-1个节点加入消息(从其他J-1个加入节点)，将在那些消息中其他节点的等级与自身等级进行比较，在以下两种情况下将自身选为临时根：i)如果节点n_i具有最大的等级；ii)如果节点在等级相同时具有最小ID。否则，设置具有最大等级或最小ID的其他节点作为其父节点以及树的临时根。

4)如果加入节点n_i在t₁时间内没有接收到任何消息(树不存在并且只有一个加入节点)，则选择自身作为临时根并开始形成树。

本发明所述的传送树的节点删除算法如图2所示，具体步骤如下：

1)当目标移动时，把从F区域移动到VF区域的节点从传送树中移出。如果树节点的剩余电池电量下降到临界值以下，则将它从传送树中移除。从传送树离开的节点将包含其所有子节点的ID的节点离开消息发送到其父节点，并将包含其父节点ID的新父节点消息到所有其子节点。

2)父节点在接收到节点离开消息时，从其子节点列表中删除相应的节点(由消息中的节点ID标识)。

3)当节点从其父节点接收到新父节点消息时，将父节点替换为由消息中父节点ID标识的新父节点。

4)当临时根节点本身从F区域移动到VF区域或其剩余电池电量可能下降到临界值以下，临时根发送子根消息给它的所有子节点。

5)接收到子根消息的节点开始新临时根的选举。每个这样的节点广播包含其ID和等级的节点数据消息，然后等待t₄时间。在该时间内，节点n_i可以接收到D个节点数据消息。然后，节点n_i将其等级与在这D个节点数据消息中其他节点的等级进行比较。如果节点n_i发现其等级是最大或者跟其他节点的等级同为最大但其ID最小，它就声明自己是新的临时根，并广播一个根选举消息来通告这个选举。否则，节点n_i将等级最大的其他节点设置为新根以及其父节点。

本发明所述的传送树的根节点选择算法如图3所示，具体步骤如下：

1)从VN区域的节点中选择根(永久)。当永久根刚离开VN区域或者其电池能量下降到临界水平以下时，永久根选举程序被触发。准备离开的根广播包含根ID、根类型和根区域的根离开消息。

2)如果树中没有节点，则准备离开的根将不会接收任何消息，并且它将继续作为临时根。

3)如果有节点存在于VN区域中，则向发送者回送节点接受消息，从而使得根接收到N个节点接受消息并将第一发送者设置为其父节点。

4)VN域中的节点在接收到根离开消息之后开始新根的选举，广播包含节点ID及其等级的节点数据消息。接收D个节点数据消息后，VN区域中的每个节点n_i从消息中找到等级最大的节点，并与其自己的等级进行比较。如果节点n_i的自身等级大于n_max的，则自身作为新的永久根并广播根改变的消息。如果等级相同，若节点n_i的ID最小，则还选择自身作为新的永久根。否则，选最大等级的节点作为新的根和父节点。

本发明所述的传送树的临时节点算法如图4所示，具体步骤如下：

1)当临时根远离目标并更改其模糊区域时，广播包含根的ID、类型和当前区域的根区域更改消息。

2)任何节点接收到该消息，比较自身区域是否比所广播的更好。如果是，则节点向临时根发送包含其ID和等级的根更改消息。

3)在t₂时间后，临时根可以接收“C”个这样的消息。在这“C”个消息中，临时根找到具有最大等级的节点，如果等级同为最大的则找到具有最小ID的节点。选择该节点作为新的临时根，并广播包含新临时根的ID、区域和类型的根更改消息，并将新根设置为其父节点。

4)任何树节点接收到根改变的消息后，更新根信息，新的根节点将其状态更改为临时根。

本发明所述的传送树的VN区域节点算法如图5所示，具体步骤如下：

1)当树节点n_i从N区域进入VN区域时，它检查现有根的类型。如果现有根是永久性根，则将根设置为其父节点(VN区中的所有节点都直接连接到根)，并将包含其ID的根加入消息发送到根节点。当永久根接收到根加入消息时，将发送者设置为其一个子节点。另一方面，如果根是临时的，则节点n_i将自身设置为新永久根，并广播包含自身ID、根类型(永久)及其区域(VN)的根改变消息。

2)当旧的临时根接收到这种根改变消息时，将发送节点设置为其父节点并更新根信息。

3)所有树节点(除了n_i)和旧根接收到根改变消息时，用消息中的根信息更新其数据库。