面向目标跟踪应用的无线传感器网络路由选择方法

摘要

本发明涉及一种面向目标跟踪应用的无线传感器网络路由选择方法，其方法是：如果要转发的数据包是由sink节点到目标区域的查询数据包，则采用一种基于目标活动区域的贪婪转发和受限泛洪相结合的转发策略；如果要转发的数据包是由目标区域到sink节点的汇聚数据包，则采用一种基于sink节点位置的贪婪转发和节点剩余能量相结合的转发策略。本发明中节点只需要维护自身状态信息，使得该方法能很好地适应在节点数量增加时的情况；采取基于地理信息的贪婪转发策略，通过减少通信跳数，减少了数据包路由的时延；转发汇聚数据包时以节点能量和距离的综合函数作为转发代价，使得汇聚数据包既可以尽快向目标节点转发，又能平衡所有节点的能量消耗，从而延长网络寿命。

说明书

技术领域

本发明属于无线自组织网络领域，特别是一种基于地理信息的面向目标跟踪应用的无线传感器网络路由选择方法。

背景技术

WSN是由大量自治的微型传感器节点以Ad-Hoc等方式构建形成，并能够协同地对某种物理现象进行感知的网络。由于该网络具有不需要固定的基础设施，可快速部署、隐蔽性、自组织性和健壮性等特点，在军事、工业、交通、安全、医疗和家庭等众多场合有重要的应用潜力和前景，是目前国内外工业界和学术界研究的热点技术之一。

WSN中节点携带的电源能量有限；单个节点通信、计算和存储能力较弱；网络的拓扑结构动态变化；与应用相关性较强等。这些特点要求WSN中的路由方法必须适应自身特点，且针对具体应用来进行设计。

应用于目标跟踪应用的WSN路由方法应满足以下需求：(1)能耗低。网络内每个传感器节点通常使用容量有限，不可更换的电池，因此，目标跟踪应用中路由方法必需采取节能策略。(2)数据传输可靠。目标跟踪对于路由数据的可靠传输有较高要求，因为如果路由数据丢失，可能造成跟踪的不准确或丢失，而目标丢失后起用恢复机制又会消耗较多系统能量，因此，应用于目标跟踪的路由方法必须能够可靠地传送数据。(3)协议可扩展。目标跟踪所采用的传感器节点数量可能会随着目标的数量，跟踪的精度等要求不断增加，因此，目标跟踪应用要求路由方法具有较好的可扩展性。为了适应拓扑动态变化的网络结构，提高系统的鲁棒性，路由方法应该采用分布式运行方式。(4)通信实时性好。在目标运动速度较快的场合，要对目标进行准确的跟踪，节点间数据通信具有一定的实时性要求。否则就无法实现对目标进行及时、准确地跟踪。

研究者已提出许多WSN路由方法。根据是否以地理位置来标识目的地，路由计算中是否利用地理位置信息，这些路由方法可分为基于地理信息的路由方法和非基于地理信息的路由方法两大类。在目标跟踪应用中，往往需要唤醒距离目标最近的传感器节点，以得到关于目标的更精确的位置等相关信息，将节点的地理位置作为路由选择的依据，不仅能够完成路由功能，还可以降低系统专门维护路由协议的能耗。因此，基于地理信息的路由方法较适合于WSN目标跟踪应用。采用基于地理信息的路由方法需要解决的一个问题是通信“空洞”问题，即数据包沿固定路径转发时，一些节点由于频繁转发数据包导致能源耗尽而失效，从而形成转发“空洞”。已提出的基于地理信息的路由方法中，GPSR(GreedyPerimeter Stateless Routing，GPSR)[Karp B and Kung H T.“GPSR：Greedy perimeter stateless routing for wireless networks”.Proceeding of the 6th annual international conference on Mobilecomputing and networking，New York：ACM Press，2000，243-254]使用贪婪转发和沿周界转发两种方法转发数据包。贪婪转发方法是基本方案，当贪婪算法失效时，GPSR通过在该区域原始网络图之上建立平面图(比如加伯利图)的方法来解决“空洞”的问题，即通过围绕平面图边界向目标区域继续转发数据包的方式来恢复路由，条件满足时又恢复贪婪转发。如此反复，直到最后到达目的地。

GEAR(Geographical and Energy-Aware Routing，GEAR)[Yu Y，Estrin D，and Govindan R.“Geographical and Energy-Aware Routing：A Recursive Data Dissemination Protocol for Wireless SensorNetworks”.UCLA Computer Science Department Technical Report，UCLA-CSD TR-01-0023，2001.]协议利用节点能量和地理信息作为启发式选择路径向目标区域传送数据。GEAR协议要求每个节点维护一个预估费用和一个通过邻居节点到达目的节点的学习费用。预估费用是节点剩余能量与到目标节点距离的综合代价，学习费用则是对描述网络中存在空洞时所需要的预估费用的改进。如果存在通信空洞，则采用学习费用代替预估费用。

以上基于地理信息的路由方法应用于目标跟踪存在以下不足：

(1)GPSR解决通信空洞的方法是沿周界转发，需要根据原始网络拓扑图生成平面图，计算复杂度较高，而且数据包不断沿着比原始网络图稀疏很多的平面图边界进行转发，容易导致平面图上的节点很快就因能量消耗殆尽而失效，造成网络分割。

(2)GEAR中一些开销小的节点负载大，从而很容易导致这样的节点能量消耗殆尽而失效；处理通信空洞中节点剩余能量信息和学习代价信息都需要进行更新传递，这就会增加网络通信量，对这些信息进行更新的时间间隔长短同时也会影响到算法的性能。

(3)GPSR和GEAR均没有考虑到目标跟踪应用背景下数据包转发的实时性要求。在遇到通信空洞时，GPSR需要耗费较大时间和计算代价进行平面图的生成工作；GEAR也需要节点间多次通信以传递能量和距离信息，以平衡网络能量消耗和贪婪转发。但在目标跟踪应用中，当遇到通信空洞时，最重要的是要做到时间上尽可能迅速地绕开空洞，以降低节点间的通信延迟，从而降低整个网络端到端通信延迟。

(4)GSPR和GEAR算法均没有考虑节点在不同状态下的能量消耗问题。

发明内容

本发明的目的是针对现有的WSN路由协议无法满足目标跟踪应用在能量效率、可靠性、实时性和可扩展性等方面的性能需求，提出一种面向目标跟踪应用的无线传感器网络(wireless sensor network，WSN)路由选择方法。

为了实现上述目的，本发明由两个部分组成：

(1)sink节点到目标的查询数据包转发方法QPR(Query PacketsRouting，QPR)：采用基于目标活动区域的贪婪转发和受限泛洪相结合的转发策略；

(2)目标到sink节点的汇聚数据包贪婪转发方法APR(AggregatePackets Routing，APR)：采用基于sink节点位置的贪婪转发和节点剩余能量相结合的转发策略。

上述方法的具体步骤为：：

步骤1：执行网络初始化过程，节点间通过信息交换获取邻居信息，并在路由表中保存一跳邻居信息；

步骤2：节点收到数据包后，首先通过目的节点ID判断该数据包是由s ink节点发出的查询数据包还是从目标区域发来的汇聚数据包；

步骤3：如果是查询数据包，则执行步骤4；否则执行步骤5；

步骤4：启动s ink节点到目标的查询数据包转发方法；

步骤41：按照贪婪转发与受限泛洪相结合的原则确定当前节点的受限泛洪区域LFZ(limited flooding zone)；

步骤42：判断LFZ是否为空集，如果为空集则执行步骤421，否则执行步骤423；

步骤421：空洞存在，放宽受限泛洪条件，重新确定节点的LFZ(relaxed LFZ，松弛的LFZ)；

步骤422：按松弛的LFZ泛洪查询数据包；

步骤423：按LFZ泛洪查询数据包；

步骤5：启动目标到sink节点的汇聚数据包贪婪转发方法；

步骤51：按照贪婪转发和剩余能量相结合的原则计算邻居节点的估计代价，找出具有最小代价的节点；

步骤52：判断该节点的最小代价是否小于当前节点的估计代价，如果不小于，则执行步骤521，否则执行步骤524；

步骤521：存在空洞，放宽贪婪转发条件，重新选择下一跳节点；

步骤522：如果所选择的节点恰好为当前节点的上一跳节点，说明存在路由死循环，转步骤523，否则转步骤524；

步骤523：启动后退一跳重新路由机制，当前节点通知其上游节点重新选择下一跳节点，且在选择时不考虑自己，上游节点转步骤51；

步骤524：该节点作为当前节点的下一跳节点；

步骤525：当前节点转发汇聚数据包。

本发明充分考虑了目标跟踪应用对WSN路由协议特定的性能需求，其优点和有益效果主要在于：

(1)所提出的方法具有较好的能量使用效率，主要体现在通过尽可能减少参与转发的节点数降低了网络能耗。如，查询数据包转发方法中采用受限泛洪和贪婪转发相结合的策略减少参与转发节点数；汇聚数据包转发方法中上游节点每次只需要转发给一跳邻居内的一个节点，而且这种转发也是“贪婪”的。汇聚数据包转发方法中还考虑了能量的均衡使用，有利于延长网络寿命。

(2)所提出的方法简单，节点不需要维持过多路由信息，只需保存一跳邻居节点的位置信息，不需要任何全局信息，可以以分布式方式进行，节点可以随意增加，可以较好适应网络拓扑结构的变化，可扩展性较好。

(3)所提出的方法采用基于地理信息的贪婪转发策略，数据包总是沿着最接近目标的方向转发，这样可以减少数据包收发方之间的通信跳数，从而减少端到端时延。

附图说明

图1为本发明数据包转发路径选择方法流程图。

图2为本发明sink节点的受限泛洪区域示意图。

图中V_min和V_max分别表示目标的最小和最大速度，O是目标在t时刻的位置，则T时刻(T＞t)目标可能存在的区域为以O为圆心，内环半径为V_min*(T-t+δ)、外环半径为V_max*(T-t+δ)的圆环区域，其中δ为sink节点到目标区域的通信时延。黑色圆点表示节点，阴影部分所含的节点即为sink节点的受限泛洪区域。

图3为本发明查询数据包路由策略示意图

图中黑色小圆点表示节点，黑色大圆点表示sink节点和目标区域中心。

图4为本发明汇聚数据包路由策略示意图

其中黑色小圆点表示节点，黑色大圆点表示sink节点。

具体实施方式

下面结合附图和实施例对本发明作进一步的详细描述。

本发明在网络建立前执行一个初始化过程，各个节点通过信息交换获取一跳邻居信息并保存在路由表中；通过现有的各种节点自定位算法，节点获取自己的地理位置。

查询数据包格式为：[ID_qrp，v^(pri)，X_O^(t)，QryData]，其中包括查询数据包ID ID_qrp，前一节点v^(pri)，t时刻目标初始估计位置X_O^(t)，以及查询的内容QryData；

汇聚数据包格式为：[ID_ARP，v^(cur)，X_s，ObjData]，其中包括汇聚数据包ID ID_ARP，当前处理节点V^(cur)，sink节点坐标X_s和探测到的目标状态数据ObjData；

数据包转发过程中，某节点收到数据包后，首先通过目的节点ID判断该数据包是由sink节点发出的查询数据包还是从目标区域发来的汇聚数据包；

实施例1：

参见图2说明本实施方式。当前节点v^(cur)收到的是查询数据包(含有ID_qrp)，v^(cur)采取一种贪婪转发与受限泛洪相结合的策略转发数据包，按照式(1)确定要泛洪的一跳邻居节点集合(称为LFZ(limitedflooding zone))：

$\mathrm{LFZ}\left(v^{\left(\mathrm{cur}\right)}\right)=\left\{v^{\left(j\right)}\right|v^{\left(j\right)}\in \mathrm{LFZ}\left(\sin k\right)\}\cap \{v^{\left(k\right)}|v^{\left(k\right)}\in \mathrm{nbr}\left(v^{\left(\mathrm{cur}\right)}\right)\},---\left(1\right)$

其中nbr(v^(cur))是v^(cur)的一跳邻居节点集合，和X_O分别表示当前节点和目标区域中心的地理位置，|X_k-X_O|和分别表示某一节点v^(cur)的某一邻居节点v^(k)和v^(cur)与目标区域中心的欧氏距离；

从式(1)可以看出，为缩小当前节点的泛洪区域，v^(cur)的下游节点应同时满足以下条件：(1)处在sink节点的LFZ中；(2)是v^(cur)的一跳邻居；(3)比v^(cur)更靠近目标。这样可以大大缩小v⁽ⁱ⁾的泛洪区域，我们称这个缩小的受限泛洪区域为LFZ。

按照这种转发策略，节点v^(cur)将在它的LFZ中泛洪查询数据包，即将数据包转发给图2(a)中阴影部分所含的节点。

如果按照式(1)，节点v^(cur)找不到合适的下一跳节点，即LFZ＝Φ，此时出现路由“空洞”，如图2(b)所示，此时，放宽式(1)的条件，按照式(2)重新选择v^(cur)的泛洪区域(我们称为relaxed LFZ)。

relaxed LFZ(v^(cur))＝{v^(j)|v^(j)∈LFZ(sink)}∩{v^(k)|v^(k)∈nbr(v^(cur))}  (2)

如何确定sink节点的LFZ呢？如图3所示，假设某目标的速度分布于区间[v_min，v_max]，t时刻目标位于位置O处，则T时刻(T＞t)目标可能存在的区域为以O为圆心，内环半径为v_min*(T-t+δ)、外环半径为V_max*(T-t+δ)的圆环区域，其中δ为sink节点到目标区域的通信时延，该数据可通过实验取一估计值。如果t时刻查询数据包p从sink节点开始泛洪，则sink只需在图3中阴影部分泛洪转发p即可，阴影部分所包含的节点集合称为sink节点的LFZ，记作LFZ(sink)。

实施例2：

参见图4说明本实施方式。当前节点v^(cur)收到的是汇聚数据包(含有ID_arp)，v^(cur)采取一种贪婪转发与节点剩余能量相结合的转发策略，选择具有最小估计代价c(v^(next)，X_s)的v^(next)作为下一跳节点：

$v^{\left(\mathrm{next}\right)}=\left\{v^{\left(k\right)}\right|v^{\left(k\right)}=\underset{v^{\left(j\right)}}{\arg \min }\left\{c(v^{\left(j\right)},X_s)\right\}\mathrm{andc}(v^{\left(k\right)},X_s)\le c(v^{\left(\mathrm{cur}\right)},X_s)---\left(3\right)$

${\mathrm{andv}}^{\left(k\right)}\in \mathrm{nbr}\left(v^{\left(\mathrm{cur}\right)}\right)\}$

其中nbr(v^(cur))是v^(cur)的一跳邻居节点集合；C(v⁽ⁱ⁾，X_s)表示节点v⁽ⁱ⁾到sink节点的代价函数。综合考虑距离和节点能量，C(v⁽ⁱ⁾，X_s)可表示为：

c(v⁽ⁱ⁾，X_s)＝α||v⁽ⁱ⁾-X_s||₂-(1-α)E(v⁽ⁱ⁾)        (4)

其中α为一可调的权值，E(v⁽ⁱ⁾表示节点v⁽ⁱ⁾的剩余能量。从式(4)可以看出代价函数综合考虑了节点与sink节点的距离和节点的剩余能量，当所有邻节点剩余能量相等或取α＝1时，这种算法就演变为传统贪婪算法即选择距离目标最近的邻节点作为下一跳节点；当距离相等或取α＝0时，选择具有最大剩余能量节点为下一跳节点。这样既使数据包尽快向目标节点前进，又能平衡所有节点的能量消耗。

具体到图4(a)中，v^(cur)按照式(3)选择下一跳节点，如果只考虑距离，则下一跳节点为节点E)。

如果在v^(cur)转发数据中，出现通信空洞，即对$\forall v^{\left(k\right)}\in \mathrm{nbr}\left(v^{\left(\mathrm{cur}\right)}\right),$均有c(v^(k)，X_s)＞c(v^(cur)，X_s)，v^(k)∈nbr(v^(cur))。这时v^(cur)无法按照贪婪转发原则找到下一跳节点v^(next)，如图4(b)所示。

这时，我们的方法是按照尽快转发原则，放宽式(3)中的条件，即v^(cur)的下一跳转发节点v^(next)只要是其邻居节点中代价最小即可，而不再要求v^(next)代价比v^(cur)更小。即：

$v^{\left(\mathrm{nest}\right)}=\underset{v^{\left(k\right)}\in \mathrm{nbr}\left(v^{\left(\mathrm{cur}\right)}\right)}{\mathrm{atg}\min \left\{c(v^{\left(k\right)},X_s)\right\}}---\left(5\right)$

从图4(b)中可以看出，如果只考虑距离，则v^(next)为节点A。一种极端的情况是按照式5求出的v^(next)恰好为v^(pri)，即v^(cur)的下一跳节点退回到其前一跳节点，如图4(c)所示。这时数据包p将在v^(cur)和V^(pri)之间来回循环转发，直至节点能量耗尽，我们称这种现象为路由死循环。出现路由死循环是由于节点密度过低引起，一旦出现路由死循环，可启动一种后退重新路由机制，由v^(cur)发送重新路由包p给其上游节点v^(pri)，告知v^(pri)出现路由死循环，由v^(pri)重新选择下一跳节点，并在选择下一跳节点时不再考虑自己(v^(cur))，这样通过后退一跳可解决死循环路由问题。此时v^(pri)按照式6重新选择其下一跳节点，记为v^(r-next))：

$v^{(r-\mathrm{nest})}=\underset{v^{\left(k\right)}}{\arg \min }\{c(v^{\left(k\right)},X_s),c(v^{\left(\mathrm{pri}\right)},X_s)\},v^{\left(k\right)}\in \left\{\mathrm{nbr}\left(v^{\left(\mathrm{pri}\right)}\right)\right\{v^{\left(\mathrm{cur}\right)}\left\}\right\}---\left(6\right)$