无线传感器网络中基于网络嵌入的弱贪婪路由协议

李志刚，陈卫卫，肖侬，夏戈明

(1. 解放军理工大学 指挥自动化学院，江苏 南京 210007；2. 国防科学技术大学 计算机学院，湖南 长沙 410073)

1 引言

传感器网络路由协议负责将数据从某个源节点通过网络多跳转发到目的节点，主要包括2方面的功能：寻找源节点和目的节点间的优化路径，将数据分组沿着优化路径正确转发[1,2]。传感器节点的能量、处理器、存储容量和带宽等性能上的局限性，使得传感器网络的路由协议设计和传统的网络具有很大的区别。比如说，在因特网的路由器上可以存储路由表，通过查询路由表来决定节点之间的路由和数据转发的下一跳节点应该如何选择。因为传感器节点的存储能力和资源不足，传感器节点不能保存大量的与路由相关的信息，所以通常采用“无状态”路由方式[3,4]。

贪婪路由就属于一种常见的“无状态”路由。在贪婪路由中，通常存在一个贪婪函数，该贪婪函数满足一定的单调性，节点可以将邻居的某些信息作为贪婪函数的参数，得到一个函数值。比较所有邻居节点的贪婪函数值大小，节点可以决定如何选择下一跳节点。其中基于地理坐标信息的贪婪路由是经常使用的路由算法。在地理贪婪路由中，贪婪函数为节点到目的节点的欧式距离，当前节点总是选择距离目的节点最近的邻居节点作为下一跳节点传输数据。地理贪婪路由的最大挑战是局部极小值问题，即当前节点找不到距离目的节点更近的邻居节点，即使当前节点到目的节点确实存在一条连通的路径，在这种情况下仍然不能保证路由的可达性。局部极小值问题是因为网络节点分布的不规则和“洞”的原因造成的[5]。为了解决该问题，研究者提出了2种方式。这2种方式可以划分为：弱贪婪路由和强贪婪路由。

弱贪婪路由方式仍然基于地理位置信息，试图“修补”贪婪路由规则。基于平面化的面路由策略属于该方式。在面路由中，如果当前节点不能找到一个距离更接近目标节点的下一跳节点的话，则放弃使用贪婪路由策略，然后按照一定的规则通过面路由绕过当前的“洞”，再重新使用贪婪路由策略。文献[4]提出如何通过平面化，以及使用左手规则(或者右手规则)来具体实现面路由。文献[6]总结了几种不同的面路由的原理和性能。不过在传感器网络中对节点进行定位是一件具有挑战性的工作，现有的定位算法计算开销和通信开销都比较大，不适合资源有限的传感器节点[7]。

强贪婪路由方式是通过找到网络的贪婪嵌入图[8]，满足全网范围内的贪婪属性。贪婪嵌入的定义为，在空间(X, d)上为无向图G定义一个映射f：V(G)→X，满足V(G)中任意2个不同的节点s，t，存在节点s的相邻节点u，满足d(f(u), f(t))＜ d(f(s),f(t))。非常遗憾的是，不是所有的有限无向图都存在一个到欧式空间的嵌入。即使某些有限图理论上存在贪婪嵌入，对于现实网络如何通过分布式算法获得该嵌入也是非常具有挑战性的问题。对传感器网络来说，为了得到贪婪嵌入将耗费巨大的能量。

本文的目标是设计一种新的弱贪婪路由协议。该路由协议要满足不需要地理位置信息或者贪婪嵌入的支持。本文的思路是首先在网络中构建基于树的网络嵌入图。在基于树的网络嵌入图中，给每个节点分配一个区间标记：[i, r]。利用节点的标记信息，设计了一种新的弱贪婪路由算法TGR。该路由算法的基本思想主要基于2种路由规则，贪婪规则和缺省规则。如果当前节点通过贪婪规则找不到满足条件的下一跳节点，则采用缺省规则寻找下一跳节点。缺省规则可以保证当前节点一定能发现下一跳节点。TGR算法能够保证无环路由，即满足任意一个节点都不可能在一条路径上出现2次或2次以上。TGR算法的另一个优点是源节点并不需要掌握目的节点的全部标记信息。通过大规模的模拟测试，TGR算法在路径长度和负载平衡方面能达到良好的性能。本文第5节还讨论了基于双树的网络嵌入图思想，在条件允许的情况下进一步提高路由算法在路径伸展因子上的性能。

2 预备知识

本文将无线传感器网络看作连通的有限无向图，下面介绍一下与本文工作相关的图论当中的图标记和图嵌入技术。

2.1 图标记机制

图标记机制是为图上的节点(或者边)按照一定的条件和规则分配一个标记的技术，被标记的图称为标记图。自 1960年以来，关于图标记机制已经有很多研究工作[9]。根据不同的目的有很多不同的种类，比如区间路由标记、距离标记、完美标记、和谐标记等。下面介绍一下与本文相关的区间路由标记和距离标记。

2.1.1 区间路由标记

区间路由又称作紧致路由机制，起源于并行和分布处理系统中处理器之间相互通信的研究[10]。 随着技术的进步，多处理器系统的规模约来越大， 但是每个处理器的存储开销是有限的，因此处理器与处理器之间的相互通信同样不能依赖于类似路由器存储表的机制。区间路由技术就是为解决这一问题提出的。其基本的思想是为处理器的每个端口标记一个区间，通过查看和比较端口的区间，当前节点可以决定将数据报文发送到哪个端口，从而实现处理器节点与节点之间的通信。图1所示为一个简单的区间路由标记图，如果节点2需要给节点4发送数据，则将数据首先发送至[3,5]标记的端口即可。

图1 区间路由标记[10]

2.1.2 距离标记

距离标记机制首次在文献[11]中提出，其目的是希望能够根据节点的标记来计算节点之间的距离。 距离标记的定义如下：给定一无向图G，d(u,v)表示图G中2点u和v之间的跳步距离。为每一个节点u赋值一个非负数的整数标记L(u)。距离解码函数f负责计算2标记之间的距离，即给定2个标记L(u)，L(v)，函数f返回f(L(u),L(v))。如果对图中的所有的节点满足 f(L(u),L(v))=d(u,v)，称(L,f)为距离标记，或者距离标记机制。

2.2 图嵌入技术

图嵌入是将Guest图G映射到Host图H上的技术。在文献[12]中定义图G的嵌入包括2个映射：1) 节点分配函数α将图G的节点一对一的映射到H的节点上；2)边路由函数ρ为图 G 的每条边(u,v)分配一条H中的路径连接α(u)和α(v)。

文献[13]利用双曲几何的理论将树状网络嵌入到双曲平面上，并且证明每个网络都可以通过构建生成树，再得到该生成树的双曲空间贪婪嵌入，从而找到原始网络的一种贪婪嵌入。该方案的问题是网络只依赖于生成树子图上的贪婪路由，浪费了有其他不在生成树上的链接，造成网络负载不均衡。

最近有关瑞奇流(racci flow)[14]应用在无线传感器网络中的工作是这方面研究的最新成果。 利用瑞奇流和双曲几何，可以通过分布式算法将网络映射到一个只含有凸洞的圆盘区域内，新的网络嵌入区域满足贪婪属性。不过该方案需要基于节点原来的坐标位置信息，而不是纯粹基于连接信息。

3 基于树的网络嵌入图

本节的核心思想是首先将网络嵌入到一棵最短路径树上，然后在该最短路径树上进行节点标记工作。不失一般性，本文对传感器网络作以下假设：1) 传感器网络是连通无向图；2) 传感器节点不需要知道自身和其他节点的位置信息；3) 传感器网络是静态的网络，或者在一段时间内保持稳定状态。

3.1 基于树的网络嵌入图构建

基于树的网络嵌入图(TNEG, tree-based network embedding graph)构建包括2步。首先在网络中构建一棵树并且统计所有节点的个数；然后从根节点开始按照自上而下的方式为每个节点分配一个标记。

3.1.1 通过最短路径树统计节点总数

首先随机选择一个节点作为根节点。然后根节点向网络中其他的节点广播“HELLO”消息。其他的节点通过收到的消息计算到根节点的最短跳步数。在该过程中，每个节点选择一个节点作为自己的父节点，所选节点的跳步数要小于当前节点的跳步数。当该过程结束以后，在网络中便构建了一棵最短路径树。此时除叶节点以外的每个中间节点可以看作一棵子树的根节点。然后每个叶节点向其父节点发送一个“COUNTER=1”的消息，当叶节点的父节点P收到所有孩子节点的“COUNTER=1”消息以后，则向自己的父节点发送一个“COUNTER=m”的消息，其中，m等于P的孩子节点的个数加 1。所有的中间节点都重复同样的操作， 直到根节点收到“COUNTER=n-1”的消息。然后根节点可以计算出整个网络的节点总数n。

在以上所有的过程中，每个节点最多只发送 2个消息，一个为“HELLO”消息，一个为“COUNTER=i”消息。每个节点可能会收到多条消息，这依赖于节点的度数。所以每个节点的收发开销平均为2Es+dEr，整个网络的能量开销为

其中，d为网络的平均度数，Ew代表整个网络的能量开销，Es为节点发送一个消息的能量开销，Er为节点收到一个消息的能量开销。

3.1.2 标记分配

第一步完成以后在网络中就生成了一棵最短路径树(SPT)，同时根节点也计算出网络的节点总数，而且每个中间节点也都计算出以自己作为根节点的子树的节点个数。接下来根节点就开始进行标记分配的过程。一开始根节点R为自己分配区间[1, n]作为其标记。查询子节点，根节点可以获得每个子节点作为根节点的子树的节点总数。假设根节点有 k个子节点C1,C2,…,Ck。Ci.count表示以Ci为根节点的子树的节点总数。根节点R保留区间[1,n] 的左边界1，然后将区间[2,n]按照 C1.count, C2.count,…,Ck.count的比例划分为k个子区间。举例说明，可以按下面的方式进行分配，将[2,C1.count+1], [C1.count+2, C1.count+C2.count+1],…, [n-Ck.count+1,n]分别分配给子节点C1,C2,…,Ck。更一般的，对中间节点 N，如果其标记为[i, r]，且有 l 个子节点 Ci1,Ci2,…,Cil，那么可以将[i+1,i+Ci1.count],[i+Ci1.count+1,i+Ci1.count+Ci2.count],…,[r-Cil.count+1,r]分别分配给子节点Ci1, Ci2,…, Cil，分配过程和根节点是一样的。标记分配过程的区间划分方式可以有多种，本节暂时不考虑具体的分配方案，在下面第5节会讨论一种基于双树的标记分配方案。

图2给出了TNEG网络的一个具体的例子。在TNEG网络中，每个节点都对应一个[i,r]的标记，称i为节点的ID，r为节点的范围。节点N的标记[i,r]作为一个整数区间包含了所有以N为根节点的子树节点的ID。

图2 基于树的网络嵌入标记

3.2 TNEG的属性

3.2.1 标记性质

对每个节点来说，其标记[i,r]满足 i≤r。通过该性质，可以将所有的节点分成3类。如果i=1，则该节点为根节点；如果i=r，则该节点为叶节点；如果i＜r且i＞1，该节点为中间节点。以节点N为根节点的子树的节点个数为r-i+1。

3.2.2 标记间的关系

假设有2个节点S：[iS, rS]和D：[iD, rD]。不失一般性，假设iS＜ iD。因为iD≤rD，所以iS＜rD。但是对节点D来说, rS有如下2种情况（如图3所示）。

图3 标记之间的关系

1) rS≥rD: 这种情况下，D是以S为根节点的子树中的一个节点。这种情况称为S覆盖了D。

2) rS＜iD: 在这种情况下，S和D分别为2棵独立子树的根，即这2棵子树没有共同的节点和边。

3.2.3 节点的知识

在TNEG中，节点N的所有邻居节点可以分成3类：一个父节点、N的孩子节点和满足第2种情况的其他邻居节点。每个节点都可以收集一跳邻居的标记信息。

定义 1 节点知识。节点自身以及所有一跳邻居节点的标记区间的并集。

通过图4可以发现以下2个性质：1)节点的知识分布是不平衡的；2)节点的知识具有局部性。下面设计的贪婪算法主要是基于节点知识具有局部性进行的。

图4 节点知识分布(网络节点个数138)

4 基于TNEG的路由算法

假设源节点为S：[iS, rS]，目的节点为D：[iD, rD]。如前所述S和D的关系如下。

1) 包含情形：iD∈ [iS, rS]；

2) 独立情形：iD∉ [iS, rS]。

对包含情形来说，肯定存在S的一个子节点C：[iC, rC]，满足iC≤iD≤rC，因此源节点S可以直接将数据发送给C。但是对独立情形而言，源节点S找不到满足 iC≤iD≤rC的子节点作为下一跳节点。对独立情形而言,可以设计以下3种算法。

4.1 基本路由算法

显然，根节点[1, n]在最短路径树上能够发现到网络中其他节点的路由方式。同理节点[i, r]能够发现ID从i到r的所有节点的路由方式。所以基本路由算法TBR(tree based routing)的思想是将数据发送给当前节点的父亲节点直到遇到包含情形为止。

4.2 基于节点知识基本路由算法

在基本路由算法中，仅使用了最短路径树上的信息，即所有的路径都是树上的路径，而不会用到除最短路径树上的链接以外的其他链接。不过在某些情况下，节点可以从非父节点和非子节点的其他节点上获得信息。如图2所示，当节点[7,8]需要查找[12,12]时，可以发现邻居节点[11,12]覆盖了节点[12,12]，因此节点[7,8]可以直接将数据发送给[11,12]，而不用发送给其父节点[4,8]。因此基于节点知识基本路由算法(tree based and one hop knowledge routing)通过查看节点的知识，获得更大的机会找到覆盖目标节点标记的节点。

4.3 弱贪婪路由算法

4.3.1 贪婪函数

贪婪路由主要关注独立情形。对第1种情况，同样使用基本路由算法，该贪婪路由为弱贪婪路由算法。设计弱贪婪路由算法的关键在于寻找一个具有局部单调性的函数。本文设计了下面的函数作为贪婪函数：

其中，sgn(n)为符号函数，当 n＞0时，sgn(n)=1；当n＜0时，sgn(n)=-1；sgn(0)=0。[x,y] 表示当前节点要考察的邻居节点的标记，满足x ≤ y。

该函数满足：1) iS＜x2＜ x1＜iD且 y1＞rS，y2＞rS；2) iD＜ x1＜ x2＜ iS时，f (x1,y1) ＜ f(x2,y2)。1)和 2)给出了关于源节点和目的节点ID的不同关系。第1种情况说明当iS＜ iD时，所有范围(y值) 大于rS的当前节点的邻居节点满足关于 x值在区间(iS, iD)的局部单调递减性，x值越大函数f值越小。同理对第2种情况满足关于x值在区间(iD, iS)的局部单调递增性。

4.3.2 路由规则

定义2 候选邻居集。C= {N|N ∈N(S)，当iS＜iD时，满足iS＜iN＜iD或者当iD＜iS时，满足iD＜iN＜iS。

其中，N(S) 表示节点S在网络中的所有邻居集合。根据贪婪函数，为独立情形定义2个规则：

1) 贪婪规则。如果C不为空，下一跳为满足min{f (iN,rN) ＞ 0, N ∈C}的节点；

2) 缺省规则。如果C=φ，下一跳节点为当前节点的父节点。

图5给出了贪婪规则。根据贪婪规则和缺省计划，设计了TGR(tree based greedy routing)算法(算法1)。如前所述TGR为弱贪婪路由算法，因为当根据贪婪规则找不到下一跳节点的时候，算法放弃使用贪婪规则而是使用缺省规则替代。算法的关键是TNEG网络中节点的知识具有局部性。如果源节点和目标节点之间的路径都是通过贪婪规则获得的，则根据贪婪函数的局部单调性可以保证该路径无环。如果路径当中的某些节点是通过缺省规则选择的，因为父节点的范围要大于等于当前节点的范围，所以所有当前节点不会在路径中出现第2次。

图5 贪婪规则

算法 1 基于 TNEG的弱贪婪路由算法 TGR(节点S)

输入：节点S的标记[i,r],目的节点ID，节点S的父节点P和在生成树T上的S的子节点集合C，以及网络上的其他一跳邻居H。

输出：下一跳节点N

1) 如果S. ID=j，则停止；

2) 否则,首先令N = P；

3) 如果i ＜ j ≤ r,则判断集合C 中是否存在满足C. ID ≤ j ≤ C. Range字节点C；

4) 如果存在,则 N = C,并输出 N,算法停止;如果不存在转到6)；

5) 判断H中的是否存在节点 H满足(H.Range-H. ID)＜R；

6) 如果存在,选择满足H. Range-H. ID最小的节点H0,N= H0；

7) 如果不存在，分为(a)、(b) 2种情况：(a)如果r ＜j，在H 中找到ID距离j最近的、满足H. ID＜j的节点作为N；(b)如果i ＞ j，在H 中找到ID距离j最近的，满足H. ID＞j的节点作为N；

8) 输出N。

5 优化讨论

为了使基于树嵌入的贪婪路由技术在性能上，特别是在路径伸展因子上得到进一步改进，本节进一步讨论并提出基于双树嵌入的弱贪婪路由技术。

5.1 无交叉连接生成树

定义 3 交叉连接。假设相邻节点的连接是一条直线段，如果2条直线段在几何上存在非端点的相交点，则称这2条连接是交叉连接。显然，如果一个图为非平面图，则肯定存在交叉连接。

3.1节给出的构建最短路径生成树的方法中，一个节点可能存在多个距离根节点小于当前节点的邻居节点，当前节点通过随机的方式选择其中一个节点作为父节点。这种方法构建的生成树，在现实的网络中有可能存在多个交叉连接。

图6 同一个网络的不同的标记嵌入

5.2 随机标记与顺序标记

在3.1节中，构建最短路径树的过程中并没有考虑和避免交叉连接存在，而且在基于一棵树的标记分配算法中也没有考虑节点之间标记如何分配，只是按照节点覆盖的节点个数按比例划分标记区间，并没有考虑相同层次上的节点标记区间的关系。这会导致图6(a)所示的节点标记在网络中的分布杂乱。比如说，在图 6(a)中，如果节点 D([4,4])需要访问节点G([6,6])，按照TBR路由算法得到的路径为[4,4]→[2,4]→[1,7]→[5,7]→[6,6]。但是如果得到的最短路径树和标记如图6(b)所示，从节点D到节点G的路径为[3,3]→[4,4]→[6,6]→[7,7]。由此可见，对同一网络的不同标记嵌入，对路由的性能有很大的影响。造成这种现象的原因，一是构建的最短路径树中存在交叉连接；二是在节点的标记分配过程中，没有考虑树的同一层节点之间的顺序关系，即节点标记能在多大范围之内满足单调性。在最短路径树中存在交叉连接，且没有考虑同一层节点标记之间关系的标记分配方式称为随机标记分配。而满足：生成的树在网络中不存在交叉的连接；同一层次的节点的标记满足顺序关系的标记分配方式，称为顺序标记分配。为了增加TNEG的局部单调性，希望得到的嵌入图是顺序标记的。不过在传感器网络中，特别是在节点信息未知，在没有全局拓扑信息的情况下，得到顺序标记非常具有挑战性。本文的策略不追求完全的顺序标记，而是尽可能得到局部顺序标记的网络嵌入。

5.3 基于双树的网络嵌入

本文的策略是利用文献[15]提出 Contour-cast技术，首先在网络中构建轮廓覆盖网。当选择了 2个信标节点(B信标和R信标)，构建出轮廓覆盖网以后，相当于构建了一种虚拟坐标系统，每个节点都拥有一个〈bluehop,redhop〉的坐标值。在该坐标系内每个节点都可以根据所在的R型轮廓(B型轮廓)来判断所在的B型轮廓(R型轮廓)的方向。基于双树网络嵌入的过程如下。

首先构建以B信标为根节点的B型树。每个节点要选择一个节点作为自己的B型父节点，选择的原则是：在所有bluehop小于当前节点的邻居中，选择redhop最小的节点作为自己的B型父节点。以 R型信标为根节点的R型树也以同样的规则建立。同样在标记分配过程中，比如说在B型树上分配标记，当前节点总是将最小的标记分配给redhop最小的孩子节点。

以上过程，通过B型和R型轮廓互为方向，保证了节点标记在分配的过程中能够在局部尽可能地达到顺序标记的要求。此时每个节点都有B型/R型2种标记，节点需要存储4个整数。称在双树网络嵌入上设计的路由为biTGR。biTGR算法原理上和前面基于TNEG的TGR没有区别，只是通过B型/R型2种标记，增加了节点标记之间包含情形的概率，限于篇幅本文省略了biTGR的伪代码。综上所述，biTGR在网络中的初始化要比TGR复杂，在内存的使用上比TGR多2个字节。但通过下面的模拟，biTGR在路径伸展性上要优于TGR。

6 性能测试

本节通过仿真实验比较上文提出算法的性能。本文的仿真环境使用NS2网络模拟平台，在一个正方形区域内部署500个节点，节点的平均度数为14，网络直径为16跳,，在仿真环境中假设节点之间如果距离小于一个阈值，则能进行直接通信，否则不能通信。本文考虑的最重要的性能指标为连接源节点和目标节点(S-D对)的路径长度、交叉链路使用情况以及负载均衡。

6.1 路径伸展性

在本测试中，随机地选择1 000对S-D对，并分别利用TBR、TBHR和TGR产生相应的路径，最后统计各个算法的路径情况。图7中x轴表示源节点和目标节点的最短路径长度，y轴表示根据相应的路由算法产生的路径跳步长度。图7计算出各种策略相对于最短路径的平均路径长度。可以看到在本测试中当S-D间最短路径长度小于11的时候，TGR的平均路径长度小于TBR；当S-D距离小于8跳的时候，TGR的平均路径长度要小于TBHR。同时看到：1)TBHR的路径长度总是好于TBR，这说明节点知识是非常重要的；2)当S-D的距离变大时，TGR的路径长度要长于TBR和TBHR。这是因为当节点的距离足够大时，其通过访问SPT得到的路径长度(即TBR和TBHR产生的路径)与最短的路径长度已经非常接近，而此时 TGR产生的路由中可能存在距离目标节点较远的中间节点。图8给出了基于双树的网络嵌入下，在路径长度方面4种算法的性能比较。可以发现基于双树网络嵌入标记的路由biTGR在性能上要优于其他3种。即使TGR的性能也获得了较大提高，这是因为在双树网络嵌入中存在更多的顺序标记。

图7 3种算法的路径平均情况

图8 在双树嵌入下4种算法的路径平均情况

6.2 交叉链路使用情况

SPT仅覆盖了整个网络的一小部分链路，因此TBR浪费了所有没有在SPT上出现的交叉链路。对TBHR来说，最多有一次机会使用没有在SPT上出现的链路。通过测试可以发现在使用没有在SPT上出现的链路上，TGR具有的较大的优势。图9显示，TGR的交叉链路的使用率平均在 40%以上， 而TGHR的交叉链路使用率随着路径长度增加而逐渐下降，当路径长度超过 10以后，其交叉链路的使用率要低于10%。

图9 2种算法的交叉链路使用情况

6.3 负载均衡

在数据为中心的传感器网络中，存储的负载均衡是非常重要的因素[16]。一个好的存储策略应该可以平衡所有传感器的负载分布。这可以避免某些节点成为瓶颈或者过早地耗尽电量，对延长整个网络的生命周期起到至关重要的作用。本文采用所有节点负载的方差定义网络的负载均衡性。在本测试中，随机选择1 500个S-D对。如果节点转发过一个数据分组，则其负载计数器加1。对TBR、TBHR和TGR 3种策略分别进行测试，按照节点的负载计数器，对节点进行降序排序。在图10中分别将3种策略的情况列出来。可以发现在500个节点当中前50多个节点在TBR算法中的负载计数器是TGR算法的2倍多。这是因为在TBR和TBHR中，根节点和根节点附件的节点负责了较多数据的转发。在TGR中，通过贪婪规则，某些节点可以绕过根节点和根节点附近的节点找到目的节点。

图10 节点负载排序

图11从单个节点的角度说明了传输负载情况。图11中对同一网络分别选择不同规模的S-D对，规模程度从50对到1 500对，以50递增。可以发现随着 S-D对规模的增大，TBR、TBHR和 TGR的负载均衡因子都不断增加。但是 TGR的负载增长速度明显慢于TBR和TBHR。

图11 3种算法的负载均衡因子

7 结束语

本文首先将传感器网络中的贪婪路由策略分为强贪婪和弱贪婪2种，分析了目前的策略的不足，提出了一种新的基于树的网络嵌入图(TNEG)的构建方法。在此基础上设计了弱贪婪算法TGR。TGR可以应用在传感器网络和分布式存储等领域。本文通过模拟验证了TGR的可行性和优势，而且讨论了通过利用基于双树的网络嵌入并进一步改进TGR的思想。未来的工作包括如何将TGR应用到动态网络中，特别是当节点失效时，如何迅速恢复网络嵌入标记。

[1] 孙利民,李建中,陈渝等.无线传感器网络[M]. 北京：清华大学出版社, 2005.SUN L M, LI J Z, CHEN Y, et al. Wireless Sensor Networks[M]. Beijing: Tsinghua University Press, 2005.

[2] 任丰原 ,黄海宁, 林闯. 无线传感器网络[J]. 软件学报, 2003,14(7):1282-1291.REN F Y, HUANG H N, LIN C. Wireless sensor networks[J]. Journal of Software,2003,14(7):1282-1291.

[3] SAKAI K, HAMILTON B R, KU W S, et al. G-STAR: geometric STAteless routing for 3-D wireless sensor networks[J]. Ad Hoc Networks, 2010, 9(3): 341-354.

[4] KARP B, KUNG H T. GPSR: greedy perimeter stateless routing for wireless networks[A]. Proceedings of the MobiCom[C]. MA, USA,2000. 243-254.

[5] WU X B, CHEN G, DAS S K. Avoiding energy holes in wireless sensor networks with nonuniform node distribution[J]. IEEE Transactions on Parallel and Distributed Systems, 2008,19(5): 710-720.

[6] FREY H, STOJMENOVIC I. On delivery guarantees of face and combined greedy face routing in ad hoc and sensor networks[A]. Proceedings of the MobiCom[C]. CA, USA, 2006.390-401.

[7] 王福豹, 史龙, 任丰原. 无线传感器网络中的自身定位系统和算法[J]. 软件学报, 2005, 16(5):857-868.WANG F B, SHI L, REN F Y. Self-Localization systems and algorithms for wireless sensor networks[J]. Journal of Software,2005,16(5): 857-868.

[8] PAPADIMITRIOU C, RATAJCZAK D. On a conjecture related to geometric routing[J]. Theoretical Computer Science, 2005, 344(1): 3-14.

[9] GALLIAN J A. A dynamic survey of graph labeling[J]. The Electronic Journal of Combinatorics, 2010,17(1):1-246.

[10] GAVOILLE C. A survey on interval routing[J]. Theoretical Computer Science, 2000, 245(2): 217-253.

[11] PELEG D. Informative labeling schemes for graphs[A].Proceedings of MFCS[C]. Bratislava, Slovak, 2000. 579-588.

[12] NEWSOME J, SONG D. Gem: graph embed-ding for routing and datacentric storage in sensor net-works without geographic information[A]. Proceedings of SenSys[C]. CA, USA, 2003. 76-88.

[13] KLEINBERG R. Geographic routing using hyperbolic space[A].Proceedings of INFOCOM[C]. AL, USA, 2007.1902-1909.

[14] SARKAR R, YIN X T, GAO J, et al. Greedy routing with guaranteed delivery using Ricci flows[A]. Proceedings of the IPSN[C]. CA, USA,2009. 121-132.

[15] LI Z G, XIAO N, LIU Y H, et al. contour-cast: location-free data dissemination and discovery for wireless sensor networks[A]. Proceedings of the ICPADS[C]. Shenzhen, China, 2009. 88-95.

[16] 李贵林, 高宏. 传感器网络中基于环的负载平衡数据存储方法[J].软件学报, 2007, 18(5): 1173-1185.LI G L, GAO H. A load balance data storage method based on ring for sensor networks[J]. Journal of Software, 2007, 18(5):1173-1185.