基于地理位置及无线传感器网络路由协议

基于地理位置的无线传感器网络路由协议Routing Algorithms Based on Location Information for Wireless Sensor Network郑锴,童利标,陆文骏摘要：基于地理位置的路由协议是无线传感器网络路由协议研究的一个重要方向。利用位置信息指导路由的发现、维护和数据转发，能够优化路径选择，减少路由能耗，实现网络的全局优化。从限制洪泛机制、虚拟分区机制、最优路由确认机制 3个方面，可以看出地理位置信息在路由协议中的重要性。关键词：无线传感器网络；路由协议；地理位置；虚拟分区Abstract:Routing algorithms based on geographical location information is an important research subject in the wireless sensor network. The routing algorithms based on geographical location information can confirm the best routing, reduce the energy consumption, and optimize the whole network. Through three aspects involving the flooding restriction scheme, the virtual area partition scheme and the best routing choice scheme, the importance of location information is seen in the routing algorithm.Key words:wireless sensor network; routing algorithm; location information; virtual area partition无线传感器网络(WSN)是将大量的具有通信与计算能力的微小传感器节点设置在无人值守的监控区域，构成的智能自治测控网络系统。在 WSN的实际应用中，尤其是军事应用中，往往需要实现对传感器节点的定位，获取监控区域的地理位置信息，因此，位置信息也很自然地被考虑到 WSN路由协议的设计中。基于地理位置的路由协议是当前路由协议研究的一个重要方向，受到了广泛关注。基于地理位置的路由协议利用位置信息指导路由的发现、维护和数据转发，能够实现信息的定向传输，避免信息在整个网络的洪泛，减少路由协议的控制开销，优化路径选择，通过利用节点位置信息构建网络拓扑图，易于进行网络管理，实现网络的全局优化。国内外的学者针对不同的应用背景已经提出了多种基于地理位置的路由协议，如何充分地利用地理信息来实现高效的路由是研究的重点。本文将具体分析地理信息在路由协议中的应用，分别从限制洪泛机制、虚拟分区机制、最优路由确认机制等 3个方面进行分析。1 基于位置信息的限制洪泛机制传统的 Flooding洪泛路由协议具有简单性和鲁棒性的优点 [1]，许多路由协议的设计中都采用了洪泛路由的思想，然而洪泛路由存在着信息重叠和信息“内爆”现象，造成了大量的信息冗余和盲目的资源浪费。利用距离、方位等地理信息来指导和限制路由洪泛，界定洪泛路由搜索区域，能够大大提高路由搜索的方向性和有效性。当在路由受限区域内没有合适的路径时，可以自适应地对洪泛区域进行调整，或采用传统洪泛的方法继续进行路由搜索。受限洪泛区域主要有距离受限域、角度受限域和矩形受限域等形式。1.1 距离洪泛受限域目的区域的位置不确定时，可以构建一种简单的距离限制域：路由搜索信息向距离信息发送节点更远的方向进行洪泛，只有距离信息发送节点更远的节点收到数据包时才进行转发，通过这种方式能够减少信息的冗余。目的区域的位置能够确定时，可以由距离目的区域更近的节点所在的区域来构成路由请求区域。如位置辅助路由(LAR)协议中确定路由请求区域的其中一种方案，便采用了这种思想 [2]。1.2 角度洪泛受限域角度限制域是根据某一个角度而确定的受限域，也就是说，位于一定的角度范围内的中间节点才能作为路由洪泛的中继转发节点。限制角度的选取有多种方法，图 1、图 2和图 3分别示意了 3种角度选取方法。 图 1中所确定的角度受限域由两条相交的射线 OM和 OP所构成 [3]，以源节点 S和目的节点 D为圆心、以 RS和 RD为半径构造了两个界限圆，不妨假设 RS >RD，可以得出两圆的公切线以及它们的交点 O，易于算出限制角∠SOM 的度数。RS 和 RD的大小根据具体应用进行设定。图 2中所确定的限制角度是变化的，而不是固定不变。S 点为源节点，D 点为目的节点，X 为一个中转节点。X 所转发的路由请求包中包含限制角∠DXM，可以根据式(1)计算：收到 X转发的数据包的节点 J和 K分别计算∠DXJ 和∠DXK，并与∠DXM 比较大小。若该角度小于限定角的节点继续转发数据包，则节点 K丢弃数据包，节点 J 将转发路由请求数据包，并且节点 J 将按照上述处理方法更新限定角的大小并继续转发数据包。图 3中源节点的路由请求数据包中包含自身的位置信息和预定的限制角度[4]，中间节点 M 收到数据包后，通过三角公式可以得出自己和源节点 S、目的节点 D间的夹角∠SMD，如果∠SMD 大于预定的转发限制角，则继续转发，否则就丢弃数据包。预定的限制角度可以根据具体应用进行设定。1.3 矩形洪泛受限域矩形限制域即是通过一定的策略所划定的矩形洪泛区域，具体给出以下两种划分方法。图 4中的矩形区域即为矩形受限域的一种构造方法。以源节点 S 和目的节点 D 作为两个顶点总可以构造矩形区域。为提高路由请求的成功率，可以将目的地扩展为一个半径为 R 的圆形区域进行优化。半径 R一般不超过节点的通信半径，其设置可以根据节点的稠密程度进行调整，一般情况下，如果节点稠密可以将 R 设定得小些，如果节点稀疏则可以将 R 设定得大些，以保证路由的成功率。 图 5中给出了另外的一种矩形受限区域 [5]，源节点 S 和目的节点 D分别作为所构造矩形两条对应边L1、L2 的中心，以与源节点和目的节点所构成的直线所平行的两条线段 L3、L4 作为矩形的另外两条边。其中 w为 L1、L2 的边长，其大小可根据具体应用进行设定。此外，通过对整个区域划分为网格，进而查询信息分别在各个矩形网格内进行洪泛，如双层数据发布(TTDD)协议 [6]，也可以理解为矩形限制域的一种构造方法。2 基于位置信息的网络虚拟分区机制基于虚拟分区的路由机制是利用地理位置信息将整个监控区域划分为若干子区域，进而利用区域的位置信息来设计路由的机制。它适合于大规模网络，可扩展性强，利用组织结构设计的方法较好地解决了大规模网络的协同问题；各分区所包含的位置信息利于路由的建立，能够实现方向性信息传输，减少信息传输的盲目性，减少信息冗余，便于信息融合和移动节点处理，信息传输的实时性好；此外通过对区域内的节点的任务分配和调度，可以使部分节点处于休眠状态，节省能量，延长网络寿命。 虚拟分区可以有多种形式，包括规则的几何网络分区、虚拟极坐标系统以及由分簇算法形成的不规则分区等。具体实现中，可以考虑将整个网络均衡地划分为网格区域；也可以根据节点密度、连通度、网络规模等信息将网络非均匀地划分为若干分区。路由搜索过程中，可分为区域内路由和区域间路由两个过程分别进行考虑。2.1 规则网络区域的划分规则网络分区可以考虑采用包括矩形、正六边形、三角形、菱形、圆形、扇形区域等多种形式。正六边形区域是借鉴蜂窝网的小区机制，由于其计算较为复杂，较少采用；圆形区域方法是通过比较分区半径和节点到分区中心点距离确定节点的所属分区，在分区的边界会有重叠；文献[7]中提出了三角形或菱形区域的分区方法，即是将网络区域划分为三角形或菱形的网格分区。文献[8]中提出了将网络区域划分为环带扇形栅格的分区方法；矩形区域划分方法不存在重叠区域，实现过程比较简单，在实际中得到了较多的采用。方形网格是最常用的矩形分区方法，是较多地采用的一种分区方式，如基于位置的能量感知路由(GAF)[9]、TTDD、基于网格的路由(GRID)、基于网格的分簇路由(GROUP) [10]等协议。本文中将对几种典型的基于方形网格的路由协议进行分析。GAF协议中，根据节点的位置信息和通信半径，将网络区域划分成若干虚拟单元格，保证相邻单元格中的任意两个节点都能够直接通信。假设所有节点的通信半径为 R，网格区域划分的边长为 r，则为了保证任两个单元格间的通信，需要满足 。网格内采用让部分节点进入休眠状态以减少能量消耗的拓扑控制算法，同时采用节点状态转换机制控制节点的状态。GAF 的核心思想是尽量通过使虚拟网格中的每个区域的代表节点总是处于激活状态模式来保持网络互联。TTDD协议中，当多个节点探测到事件发生时，选择一个节点作为发送数据的源节点。源节点以自身作为格状网的一个交叉点构造一个格状网。其过程是：源节点先计算出 4个相邻交叉点的位置，利用贪婪算法请求最接近交叉点位置的节点成为转发节点，转发节点继续这个过程直至请求任务超时或到达网络边缘。转发节点保存了事件和源节点的信息，是以后进行数据传输的参与者。在汇聚节点进行数据查询时，汇聚点的查询请求采用洪泛的方式在在交叉点间传播，直到源节点收到查询请求，数据反向传送到汇聚节点。GRID协议中整个网络被分成若干固定大小的虚拟网格，路径由一组特定的虚拟网格组成。每个网格中通过一定的方法选取一个节点作为网关，负责所有经过本网格的数据包的转发，路由采取从网格到网格的方式。文献[5]中给出了多种网格边长的确定方法，其中，若设节点的通信半径为 R，网格边长为 r，则当满足 时，就能保证对角的相邻网格间节点的通信畅通，即能满足八向邻域网格间的通信。GROUP协议中，每隔一定的时间，由 Sink点选出网格种子节点，进而建立以网格种子节点为基准点的一定宽度的虚拟格子。每个网格中选举出一个节点作为簇头节点，簇头节点一般接近网格交叉点，在簇头节点周围一定范围内的节点都属于该簇。2.2 虚拟极坐标系统 虚拟极坐标系统是一种较为特殊的角度分区方式，适用于数据中心存储方式的地理位置辅助路由(GEM)协议[ 11]基本思想便是建立一个虚拟极坐标系统来表示实际的网络拓扑结构。网络中的节点形成一个以汇聚节点为根的带环树，每个节点用到树根的跳数距离和角度范围来表示，节点间的路由通过这个带环树来表示。虚拟极坐标系统建立过程为：由汇聚点将角度范围分配给每个子节点，如[0，90]。每个子节点得到的角度范围正比于以该节点为根的子节点的数目。每个子节点按照同样的方式将自己的角度范围分配给它的子节点。这个过程一直持续进行，直到每个叶节点分配到一个角度范围。这样，节点可以根据一个统一的规则(如顺时针方向)为子节点设定的角度范围，使得同一级节点的角度范围顺序递增或递减，于是到汇聚点跳数相同的节点就形成了一个环形结构，整个网络则形成一个以汇聚节点为根的带环树。其基本的路由过程为：节点发送数据时，若目的位置的角度不在角度范围内，就向父节点传递该消息，父节点也采用同样的方式处理该消息，直到消息到达了包含目的节点的位置角度的节点。2.3 基于分簇算法的不规则分区位置信息在分簇路由中也能够得到重要的应用，根据不同的分簇算法所形成的各个簇往往同时构成了不规则的网络虚拟分区。簇头的产生是簇形成的基础，簇的位置信息是簇头选择算法的一个重要准则，这些地理信息包括节点距簇头的距离、簇头距基站的距离、距离能耗比等信息。如基于模糊逻辑的簇头选举(CEFL)算法 [12]将节点向心性作为一个簇头选举的准则，向心性即节点靠近簇中心的程度，用该节点到簇内其它节点的距离平方和来度量。簇头产生之后，周围节点根据簇头的分布选择所加入的簇，位置信息同样会得到应用，如在基