基于距离和角度的无线传感器网络路由方案

Compu~rEngineeringandApplications计算机与应用 2010，46(31) 109 基于距离和角度的无线传感器网络路由 谢志恒 ，张向利 ，何 龙 ，黎 勇 XIE Zhi—heng ，ZHANG Xiang-li ，HE Long ，LI Yong 1．桂林电子科技大学 信息与通信学院 ，广西 桂林 541004 2．桂林电子科技大学 计算机与控制学院，广西 桂林 54 1 004 1．Information & Communication College，Guilin University of Electronic Technology，Guilin，Guangxi 54 1 004，China 2．Department of Computer and Control，Guilin University of Electronic Technology，Guilin，Guangxi 541004，China E—mail：heng@mails．guet．edu．cn XIE Zhi-heng，ZHANG Xiang—li，HE Long。et a1．Distance and direction based routing scheme in wireless sensor net- works．Computer Engineering and Applications，2010，46(31)：109—110． Abstract：A new distance and direction based routing(DDR)scheme，which combines distance based and direction based geographical strategy as the standard for selecting the next hop，is proposed．The results of simulation experiments show that DDR achieves an efficient trade·off between energy consumption and delivery latency．The overall performance of DDR in terms of energy consumption and delivery latency is better than those of both only distance based and direction based scheme． Key words：wireless sensor network；geographical routing；distance and direction 摘 要 ：综合 了基于距离和基于角度的两种路 由方案的优势，提 出一种新的基于距 离和角度的路 由方案DDR(Distance and Di． rection based Routing)，将它作为选取下一跳的评判标准。仿真结果表明，DDR能够在能耗和延时之间达到有效的折中，其综合 能耗和延时性能要优于单一的基于距离和基于角度的路由方案。 关键词：无线传感器网络 ；地理路由；距离和角度 DOI-10．3778／j．issn．1002—8331．2010．31．030 文章编号：1002—8331(2010)31．0109．02 文献标识码：A 中图分类号：TP393 1 前言 随着GPS等定位技术的发展，传感器节点可以方便地获 得本身、邻节点及 目的节点的地理位置信息 ，地理路由正是基 于这些位置信息的路由方案 】，它与基于拓扑的路由方案相 比，能够很好地适应网络拓扑的动态变化，当由于移动或者节 点失效造成拓扑变化时，地理路由可以按照某种策略简单地 选择另一个有效的邻居节点作为下一跳来实现路由恢复；其 中贪婪地理路由在整个数据的传输过程中不需要建立和维护 路由也不需要存储路由信息，只要求网络中每个节点准确地 存储周围邻节点的状态信息即可降低节点的能耗和内存，同 时它能够提供很好的数据传输保证 ，具有良好的网络可扩展 性和鲁棒性，更适合大规模的无线传感器网络。 常见的地理路由方案主要是基于距离或者基于角度的。 其中贪婪边界无状态路由GPSR(Greedy Perimeter Stateless Routing)。 是最具代表性的基于距离的地理路由方案，它使用 贪婪算法建立路由，当某个节点需要向目的节点发送数据包 时，它将会选择自己的所有邻居节点中距离目的节点最近的 节点作为数据包的下一跳，如图1所示，节点 需要选择下一 跳 ，根据GPSR算法，节点 将会被选择，那么相对于目的节点 D，数 据 包 前 进 的 距 离 尸=dist(S，D)一dist(A，D)，其 中 dist(S，D)表示节点 与节点D之间的欧氏距离，尸最大的节点 则被选为下一跳节点。当P≤0时，贪婪路由方案失效，这时 就遇到了所谓的路由空洞(void)。GPSR在平面子图中使用 右手定则采用边界路由方式绕过该void区域。 图 1 基于距离和基于角度的路由方案 另一种为基于角度的路由CR(Compass Routing) ，这种 基金项 日：广西自然科学基金(the Natural Science Foundation of Guangxi of China under Grant No．桂科自0832246)；广西青年科学基金项 目 (No．桂科青0832084)。 作者简介：谢志恒(1982-)，男，硕士，主要研究方向：无线传感器网络 ；张向利(1968一)，女 ，博士 ，教授，主要研究方向：计算机应用；何龙(1978一)， 男，硕士，主要研究方向：实时调度算法；黎勇(1978．)，男，硕士，主要研究方向：密码学，数字签名。 收稿日期：2009—03—24 修回日期：2009—05．25 Computer Engineering andApplications计算机工程与应用 方案在选择下一跳时考虑的是下一跳节点和源节点之间连线 与源节点和目的节点之间连线的夹角。在图1中，节点 的邻 居节点 的偏移角为 和 的连线与 和D的连线的夹角 。 CR路由方案将选择具有最小偏移角的节点作为下一跳节点， 图1中B将被选作为下一跳节点。与基于距离的路由方案相 比，基于角度的路由方案倾向于沿着节点 与目的节点D之间 的直线方向进行路由，但可能需要更多的跳数。 2 基于距离和角度的路由(DDR) 2．1 DDR的提出 在基于距离和基于角度的路由方案中，不论是GPSR还 是CR，它们选择下一跳时都只满足了距离或者角度一个衡量 标准。如图2所示，源节点 要向目的节点D发送数据，若采 用GPSR协议 ，它将选择距离 目的节点D最近的(即P最大)的 邻居节点 作为下一跳，但是存在另一个邻居节点B，它向目 的节点D前进的距离P比 略小一点(或者相等)，但是它的偏 移角比节点 的更小，更靠近源节点 与目的节点D之间的连 线，很显然，选 比选A要好；另一方面，采用CR协议时，也存 在这种情况，即在偏移角最佳的节点，所具有的P又太小(如 图2中的节点c)，往往不如偏移角略大且P也大一些的节点 (如图2中的节点E)。因此应该把距离和角度结合起来作为 选择下一跳的衡量标准，这样选出的下一跳在距离和角度上 都具有较好的性能。 一 ‘—＼ 三 ／ 图2 基于距离与基于角度的路由方案比较 如图2所示，在节点 和 的对比中，如果加上角度的比 较，则 应该比 好；在C、E的比较中，如果加上向目的节点 前进的距离P的比较，则很容易知道节点E比C好。这里我们 注意到余弦的特性 ，它不仅具有对称性 ，而且其数值范围在0 和I之间，所以将向目的节点前进的距离尸与角度的余弦的 积作为新的度量标准，即尸⋯=户×COS ，这样既满足了基于 距离的要求：向目的节点前进的距离最大(即离目的节点最 近)的节点优先转发，也满足了基于角度的要求：角度最小的 节点优先选择。 2．2 DDR的路由过程 DDR路由方案也是利用节点的地理位置信息使用贪婪 蒿’O．22 占o．20 0．08 耋o·06 100 15O 200 250 Maximum Transmission Range／m 图3 延时的比较 l 莹 算法来建立路由，与GPSR唯一不同的就是在选择下一跳时， GPSR仅仅是利用到目的节点的距离来做选择，而DDR不仅 考虑了距离还考虑了角度。当节点 需要向目的节点D转发 数据包时，它首先在自己的所有邻居节点中选择一个P⋯最 大的节点作为下一跳，然后将数据包发送给它，这个过程一直 重复，直到数据包到达 或者遇到路由空洞(void)。当遇到 void时，DDR跟GPsR一样，仍然利用边界转发策略来进行路 由，直到到达D或者找到能够恢复贪婪算法的节点继续使用 贪婪算法进行路由。 3 DDR方案的仿真分析 使用NS2 仿真工具来评价DDR方案的性能。通过与 GPSR和CR在不同的节点传输半径下性能的比较来验证 DDR的有效性，重点考察随着节点传输半径R的变化，从源节 点到目的节点的延时和路径能耗以及它们的乘积。 仿真平台：ubuntu8．04+Ns2．3 1； 仿真环境：在长2 000 nl、宽200 m的长方形区域中用200 个节点来进行仿真实验，假设节点在所有场景中都是随机运 动的，MAC层采用802．11DCF算法，信道带宽设为1 Mbit／s， 数据分组大小为1 kbyte，控制信息包大小为128 byte，传感器 发送数据包的间隔为1 S，节点的广播时间间隔为5 S，仿真时 间为 1 200 S。 在网络场景设置中，源节点和 目的节点分别放在网络的 两端，这里选取长方形的网络模型的目的是在相同的仿真环 境下，数据包能够经历更多的跳数，仿真环境中的广播时间间 隔为节点广播消息的间隔，该消息使得邻居节点及时更新邻 居信息表。这里采用二次方路径损耗的自由空间传播模型t71， 那么总的路径能量可以利用下面公式计算： Ⅳ E=∑[c 。+ecj 1 式中Ⅳ为从源节点到目的节点总的跳数， 为第k跳的距 离，C是和数据包大小以及每比特能量消耗有关的一个常数， e 是一跳成功的数据传输所需的控制开销。 下面 在100 m与250 m之间取值，做一系列实验，比较 GPSR、CR与DDR的性能。 在图3中，随着 的增加，所有方案的延时均减小。 越 大，跳数越少 ，因此延时越小。DDR的延时性能接近 GPSR， 而CR的延时大于DDR和GPSR。CR导致延时较大的原因是 它仅仅考虑了角度的因素，而忽略分组向目的节点的前进距 离，虽然CR方案能够使路径的总的欧氏距离最短，但同时也 导致了更多的跳数和更大的延时。如图4所示，跳数曲线与 延时曲线展现相同的趋势。 在图5中，所有方案的能耗随着 的增加而增加。R越 大，每跳距离越大，虽然跳数减少了，但是比起跳数而言，每跳 Maximum Transmission Range／m 图4 跣数的比较 一 0 100 150 200 250 Maximum Transmission Range／m 图5 平均路径能耗的比较 (下转147页) } l × × × × 4 2 O 8 2 2 2 l O O O 0 O 0 X × × X × × 6 4 2 O O 0 i 1 oo 6 。嚣g Av 苗】I8 9 e 余建坤，沈小虎 ：一种Vague集上的直接聚类法 为4类：{u1}，{”：， 4}， }， }；而直接聚类法却出现两种分类 结果，即当阈值 ，由0．84增加到O．88时，直接聚类法能够将 u，和u 分为两类。同样的现象也出现在剩下的3组实验结果中。 (2)将表2中的数据作为一个整体来看待 ，当阈值从 0到 1 变化时，传递闭包法对 的聚类结果共有5种情况：分为 1类： {／2】，／22，／23，／24，／25)；分为2类 ：{／2】，u2，u3，u4}，{ 5)；分为 3类 ： {／21，“3}，恤2， 4}，{“5}；分为4类：{u1)，{“2，"4)， 3)， 5}；分为5类 ： }，{” )，{“。)，{ )， }；采用直接聚类法的聚类结果则有8种情 况 ：分为 1类 ： l，”2，u3，u4，u5)；分为 2类：{ 1，“2，／23，／24)，{ 5}， {“1， 3，／24，ll5)，{"2)；分为 3类 ： l，／23}， 2， 4}，{“5}， 1，U3，／24}， { 2}，{ 5}；分 为 4类 ：{／21}， 2， 4}， 3)，{／25)，{Ul，／23}， 2}，{ 4}， {“5)；分为5类：{“1)，{”2)，{“3)， 4)， 5}。 对实验结果进行进一步分析，可以看出直接聚类法的分 类粒度比传递闭包法的小，这就表明传递闭包法在矩阵复合 运算中确实丢失了部分原始信息，才会出现分类粒度变大这 种情况，而本文给出的直接聚类法可以避免原始信息的失真。 5 结论 在 Vague集相关理论的基础上给出了建立Vague相似关 系的几种 ，并引入了Vague关系图，在此基础上给出了两 种Vague集上的直接聚类的方法，即编网法和最大树法，并以 文献[1]中的一个例子分别采用Vague传递闭包法和Vague直 接聚类法聚类来进行实验对比分析。实验结果表明，Vague直 接聚类法计算简单，分类粒度更小，不会造成原始信息的失 真，这是因为Vague等价聚类法需要对Vague相似矩阵进行时 间复杂度为o(n lb )的矩阵自乘运算，虽然王丽珍在文[7]中 采用一种特殊的数据结构“二叉划分树”将矩阵自乘运算的时 间复杂度降至O(m )，其中 一1≤m≤1／2n(n一1)，但是在此计 算过程中由于矩阵自乘运算的存在，从而不可避免地会丢失 原始信息，而直接聚类法不需要进行矩阵自乘运算便可得到 聚类结果，因此比Vague等价聚类法更加有效。 参考文献： [1】唐志刚，梁家荣 ，李士勇，等．Vague的等价聚类分析[J]．计算机工程 与，2007，28(9)：l992．1994． [2】Zadeh L A．Fuzzy sets[J]．Information and Control，1965，8(3)： 338—353． [3]Gau W L，Buehrer D J．Vague sets[J]．IEEE Transactions on Sys- tems Man and Cybernetics，1993，23(2)：610—614． [4]梁家荣．Vague关系[J]．计算机工程与应用，2005，42(30)：10．12． [5]杨纶标 ，高英仪．模糊数学原理及应用[M】．4版．广州 ：华南理工大 学出版社，2006． [6]周晓光，谭春桥，张强．基于Vague集的决策理论与方法[M]．北京： 科学出版社 ，2009． 【7]王丽珍．一种基于语义贴近度的抽象归纳法[J]．计算机学报，2000， 23(10)：1114—1121． [8】Chen Shyi—ming，Tan Jiantr mean．Handling multicriteria fuzzy decision making problems based on vague set theory[J]．Fuzzy Sets and Systems，1994，67(2)：163-172． [9]Dug Hun Hong，Chul kim．A note on similarity measures be— tween vague sets and between elements[J]．Information Scienc— es，1999，115(1)：83．96． [10]要瑞璞 ，沈惠璋．Vague集多属性决策的可能度法[J]．计算机工程 与应用，2010，46(2)：29—30． (上接 110页) 距离在能耗中为主导因素，因而能耗越大。三种方案比较， GPSR的能耗要大于DDR和CR。 GPSR仅仅考虑使分组向目的节点的前进距离最大，而忽 视了这一做法会导致更大的每跳欧氏距离，因此比基于角度 的路由方案需要更大的能耗。虽然DDR的能耗大于CR，但 是DDR的延时小于CR。 本文用能耗与延时的乘积来评价这三种路由方案的综合 性能。在图6中，DDR的能耗与延时的乘积最小，表明DDR 比GPSR和CR的综合性能更优。GPSR通过牺牲能耗来获得 较小的延时，而CR虽然节约了能耗，但是引入了较大的延 时。比较而言，DDR达到能耗和延时的有效折中，因此整体 性能更优。 100 150 200 250 Maximum Transmission Range／m 图6 综合性能的比较 4 结论 提出一种新的基于距离和角度的路由方案，能够在传感 器网络应用并达到能耗和延时性能的有效折中。在DDR中， 源节点首先根据自己、各邻居节点以及目的节点的坐标计算 出所有邻居节点的P⋯ ，然后选出P⋯最大的邻居节点作为 下一跳节点，该过程一直重复。当遇到路由空洞时，仍采用边 界路由来恢复路由，直到到达目的节点。通过NS2仿真评估 了DDR的性能，根据仿真结果，可以得出：对于能耗和延时的 综合测度，DDR比GPSR和CR有着更好的综合性能。 参考文献： [1]张衡阳，李莹莹，刘云辉．基于地理位置的无线传感器网络路由协 议研究进展[J】．计算机应用研究 ，2008，25(1)：18．19． [2]Xing G，Lu C，Huang Q．Greedy geographic routing is good enough in sensing covered networks[C]／／IEEE INFOCOM，2004． [3]Karp B，Kung H T．GPSR：Greedy perimeter stateless routing for wireless networks[C]／／ACM~EEE International Conference on M obile Computing and Netw orking．Boston，Massaehuse~s， United States，2000：243—254． [4]李晓维，徐勇军，任丰原．无线传感器网络技术[M]．北京：北京理工 大学出版社，2007：50—54． [5]Kranakis E，Singh H，Urrutia J．Compass Routing on Geometric Networks[C]／／Proceedings of CCCG’99，1999：51-54． [6]6 徐雷鸣 ，庞博 ，赵耀．NS与网络模拟[M】．北京 ：人民邮电出版社， 2003． [7]Rappaport T S．Wireless communications：Principles& practice[M]． [S．1．]：Prentice Hall，2002． O O 0 O O 0 O 缸 } { 1 q丑章 H。口