基于虚拟网格的无线传感器网络高可靠性路由_闫斌.doc

《基于虚拟网格的无线传感器网络高可靠性路由_闫斌.doc》由会员分享，可在线阅读，更多相关《基于虚拟网格的无线传感器网络高可靠性路由_闫斌.doc（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 基于虚拟网格的无线传感器网络高可靠性路由 $ 肖域 1+ ，周小佳 王厚军 郎方年 2 ,李本亮 1 电子科技大学自动化工程学院，四川成都 610054) 2(重庆大学计算机学院，重庆 400044) High Reliability Routing for Wireless Sensor Networks Based Virtual Grid YAN Bin1+， ZHOU Xiao-Jia1， WANG Hou-Jun1 , LANG Fang-Nian2 , LI Ben-Liang1 College of Automation, University of Electronic Sc

2、ience and Technology of China, Chengdu 610054, China) 2(College of Computer, Chongqing University, Chongqing 400044, China) + Corresponding author: E-mail: Yan B, Zhou XJ, Wang HJ, Lang FN, Li BL. High reliability routing for wireless sensor networks based virtual grid. Journal of Software 2009,20(

3、6): 1591-1601. http:/ Abstract: In order to achieve an efficient and highly reliable data delivery channel, this paper present a grid-based high reliability routing (GHRR) after comparing some communication schemes and their reliability. GHRR assign a virtual ID for every grid and its cluster head.

4、After that, the node selects its next hop nodes by itself according to the assigned virtual ID. Multiple copies of data are interleaved transmitted directly to sink. As a result, the reliability of data delivery is enhanced. The performances of GHRR has been evaluated through both analysis and exten

5、sive simulation. They show that GHRR yields an improvement in enhancing reliability and reducing time delay. Key words: wireless sensor networks; virtual grid; routing; reliability; cluster 摘要： 为了得到能量高效、具有高可靠性的数据通信链路 ,在比较几种不同通信方案的链路可靠性的基础上， 提 出了一种基于虚拟网格单元的高可靠性路由算法 (grid-based high reliability routin

6、g,简称 GHRR).算法为 每个网格及 其簇头节点分配一个虚拟 ID,节点根据该 ID 自主选择其多个下一跳头节点，使数据的多个拷贝在 朝向 sink 方向上 交错传播，从而提高数据传输的可靠性 .通过分析及仿真进一步表明，算法提高了路由的可靠 性，并具有更小的时间 延迟 . 关键词 ：无线传感器网络 :虚拟网格 :路由 :可靠性 : 簇 中图法分类号 ： TP393 文献标识码： A 无线传感器网络是由数 a 众多的单个节点通过一定的机制组成协同工作的网络 .共同完成监测 区域的数 据 感知 .为数据传输而设计的路由协议很多是在数据通信可靠的假设下设计的 .但实际环境一般不能保证可靠 通

7、信 .一些不确定因素比如节点能 a 耗尽、意外破坏等可能导致节点失效 .噪声干扰、数据冲突等也增加了通 信 链 路 的 错 误 率 . 在 算 法 设 计 中 . 必 须 考 虑 在 不 可 靠 链 路 下 如 何 实 现 可 靠 通 信 . 现 有 的 路 由 要 么 为 单 路 径 (single-path), 要么为多路径 (multi-path)方式 .显然，在单路径方式下，路径上的任何一跳节点 失效或者通信 * Received 2007-12-06; Revised 2008-02-01; Accepted 2008-03-31 点的多条路径，数据的多个拷贝通过建立的多跳路径同时向

8、目的节点发送 .虽然多路径的通信方式在一定程度 上提高了数据传输的可靠性，但整个系统能量消耗比较大，使得网络的生命周期减小 .可见 ,能量的高效性、数 据 通信的可靠性是无线传感器网络路由设计中需要考虑的两个重要方面，两者往往相互制约 .在设计路由算法 时， 需要考虑在提高链路 可靠性的前提下减少能量消耗 . 从 基 站 的 角 度看 ， 在 无 线 传 感 器 网 络 系 统 的 很 多 应 用 中 ， 基 站 是 一 个 很 特 殊 的 装置 ， 其 性 能 往 往 高 于 普 通 传 感 器 节 点 ， 而 且 一 般 不 受 能 量 限 制 ,可 以 作 为 一 个 特 殊 的 sin

9、k 在 算 法 设 计 中 加 以 充 分 利用 .在 单 sink 的 系 统 中 ， 特别 是 对于大规模 无 线传感器网 络 系统，大量 的 数据都要通 过 指向 该 sink 的特 定 路径来传 输 ，一 方面 容 易 形 成 “ 网 络 热点 ” ， 使 得 sink 周 边 节点因 为 进行 大 量数据 转 发而 能 耗过 快 ;同 时 ，多个 数 据通 过 狭窄且 相 对 单 一 的 路 径 传输 ,数 据 冲 突 加 剧 ， 延 迟 增 加 .而 对 于 两 个 甚 至 多 个 sink 节 点 的 系统 ， 数 据 可 以 通 过 多 个 sink 节 点 同 时进行 收 集

10、 ， 分担了 单 sink 的 负 荷，也 在 一定 程 度上避 免 了网 络 热点的 出 现， 并 减小了 数 据延 迟 .比 如 在军事 应 用中，要 监 测前沿 阵 地敌方活动 情 况，可以通 过 在阵地上抛 洒 无线传感器 网 络节点形成 自 组织的 网 络 ， 同 时 ,在 己 方 阵 地 两 端 部 署 两 个 高 性 能 的 sink 负 责 收 集 各 节 点 发 来 的 数据 .这 种 双 sink 的 架 构 利 用 了 基 站 的 充 足 资 源 ， 有 助 于 分 担 节 点 的 负 荷 . 1 相 关 工 作 传统无线传感器网络路由设计都采用了单 sink 的模式 .

11、如前所述，随着网络 复杂度的増加，单 sink 的网 络架 构在很多方面已不能满足系统要求 .Pink 等人在文献 1中对单 sink 作了进一步的分析，指出随着多条路 径都最 终汇聚于单个 sink,中间转发节点的争抢将越来越激烈 ,数据冲突增加，而且越靠近 sink,这种现象越严 重 .此时通 过提高节点竞争力已无法改善多路径模式下的数据传输效率，并提出一种基于多 sink 的数据传输 策略，将多个 sink 节点部署于监测区域周边，节点采集的数据通过不同路径发送给就近的 sink 节点 .此外， 文献 2,3等都采用 了多 sink 的网络模型进行网络拓扑、最优路径等的设计 . 为了解决

12、不可靠链路下的通信可靠性问题，很多算法被提出，比较典型的如下： 文献 4,5提出单路径路由修复技术，以最低能耗成本实现高可靠性的数据通信，但一般网络延迟比较大 . Stann 等人提出 RMST算法，通过探测失效链路并请求重传的方式提高路由可靠性 .文献 7,8基于端 -端可靠 性 约束建立数据通信链路，将信息按重要程度期望的可靠性等级，并以单路径重传、多路径冗余等方式建立 路由 . Suman 等人在文献 9中提出单跳距离最短路由并不能保证整个 链路上的能耗最优，并分析了在多跳链 路中跳 数、错误率的变化对整个链路能耗的影响 .在 Fan 等人所描述的 GRAB 算法 1 中 ,Sink 首

13、先通过泛洪 的方式在 网络中广播 ADV 信息包来建立数据传输的代价场，代价场暗示了一个指向 sink 的全局数据传输方 向 梯度， 这样，节点不必考虑其下一跳节点是谁，只需在其数据包中包含该节点的通信代价 ,只有通信代 价更小的邻居节 点才能继续转发该包，而通信代价相等或者更高的节点丢弃数据包 ,多个代价递减的路径交错 形成一个数据转 发的交错网 .同时，源节点 通过分配信用度的方式决定网络扩展的宽度，节点根据接收到的信 用度份额来决定是 否扩展网孔 ,从而限定数据传输的路径数，将路由限制在源节点到目的节点之间的一条狭长 的地带内，避免无限 宽度的交错路径网 .GRAB 在一定程度上保证了数

14、据传输的可靠性，不过，该算法本质上 还是一个周期性的泛洪 算法，因为每个节点代价值的取得需要一个完整的泛洪过程 ,能耗成本较高，时间延迟 较大 . 本文针对大规模无线传感器网络，并在 GRAB 算法思想的基础上提出一种基于虚拟网格的高可靠性路由 算法 (grid-based high reliability routing,简称 GHRRX 采用双基站的网络架构 ,把构建梯度的任务由各个传感 器节 点转移到两个基站，避免了节点周期性的泛洪过程，从而减轻了传感器节点的路由建立和维护负担，降 低了能 耗 .GHRR 为每个虚拟网格单元及其簇头节点分配了一个虚拟 ID,节点根据该 ID 自主选择其多

15、个下一 跳簇头 节点 .使数据的多个拷贝在朝向 sink 方向上交错传播 .从而提高了数据传输的可靠性 . 2 网 络 模 型 及 问 题 陈 述 2.1 虚拟网格的形成 在本算法中，设监测区域为边长 M 的正方形，两个高性能基站 (base station，简称 BS)分别部署于监测 区域同 侧的两端 ,其能量不受限且功率等级大小可离散调节，最大功率等级设为 T;功率等级越高，其通信覆 盖范围越广， 反之越窄 .基站相邻功率等级的覆盖范围形成一个环状区域，两个基站各自形成的环状区域相互 交叉，将目标区 域划分成一系列虚拟网格单元： 首先，两个基站 (51,552)分别按从小到大的离散功率等级

16、 1 T 广播初始化消息，初始化消息包含当 前基站 编号 (凡 5 ID)、基站的功率等级编号 (level)等信息 .目标区域内的节点收到基站广播的初始化消息 后，首先解析 基站及功率等级编号，确定自己分别处于基站 1 和基站 2 的哪两个相邻功率等级形成的环内， 节点的逻辑 ID 定 义为两个基站相邻功率等级编号的组合 ,且基于 5 幻的两位等级编号在前，基于 5S2 的两位 编号在后 .例如，某节 点分别收到来自以功率等级 5(其相邻功率等级为 4)和来自 5S2 以功率等级 8(其相邻功 率等级为 7)广播 的初始化消息，则该节点的逻辑 ID 为 4578.为避免节点 在收到新的初始化

17、消息后逻辑 ID 被 重新分配，则设定了 逻辑 ID 的节点不再接收基站广播的其余初始化消息，除非基站发出系统重新初始化的指 令 . 另 一 方 面 ,虚 拟 网 格 单 元 的 逻 辑 ID 分 配 方 式 与 节 点 逻 辑 ID 相 同 ， 即 以 两 个 基 站 的 相 邻 功 率 等 级 编 号 作 为 本 节 点 的 逻 辑 ID.显 然 ,在 同 一 个 虚 拟 网 格 单 元 内 的 所 有 节 点 逻 辑 ID 是 相 同 的 ， 都 等 于 该 虚 拟 网 格 单 元 的 逻 辑 ID.如 图 1 中 ID 为 4578 的 网 格 单 元 代 表 基 站 51 以 相 邻

18、 功 率 等 级 4,5 广 播 形 成的 环 45,52 以 相 邻 功 率 等 级 7,8 广 播 所 形 成的 环 78 的 交 叉 区 域 .在 基 于 自 由空 间 模 型 i?=c2 的 假 设 下 ，调 节 基 站 功率 等 级 以 T2 倍 递 增 ， 虚拟网格单元形成以后，每个网格单元中的所有节点形成一个簇，并选择一个簇头 .簇头负责本区域内节 点 信息的收集 .同时，所有簇头节点形成一个上层网络，负责以多跳方式向基站转发各个簇头的数据 .本文研 究各 个簇头节点 (以下简称节点 )如何形成高可靠性的网络架构，底层数据的收集、簇头的选择方法不在本文 描述范 围之内，详见其他文

19、献 . 2.2 通信模型及半径的设定 设节点通信半径固定，且覆盖其邻居节点，考虑最坏情况，如图 2 所示，节点通信半径 满 足： 2Vr2 +r22-Jlr 其中， r 为虚拟网格的边长 .设每个基站以 rt 功率等级广播信息将目标区域划分为 rt 虚拟网格，则 显然 .每个网格的边长为 ; V2M 由公式 (1)公式 (3)，节点通信半径固定为 d =22r - AM (4) 通信模型采用文献 11所给出的自由空间模型，忽略节点接收、处理数据包的能耗 ,则节点 j 向节点 y+l 的 单次通信消耗表示为 E(j, j +)=c-dJJ +1=c- d (5) 其中 , +1 为节点 y 和

20、J+1 之间的距离，为常数，且 2;)， 近 抓 2侧 的 下一 跳 邻居 节 点集 为 攸 ?2=(:;+1， +2,少 厂 1,只 )， (工 ;， Xi +1 ,y -1 1 ,xhy -1 ,y,) . 比如，节点 z 的逻辑 ID 为 5667,则其近 551 侧邻居节点有 3 个，分别为 4578,4567,4556,而 4556,5656,6756 为其近 352 侧的邻居节点，如图 1 所示 . 定义 3. 链路负荷为从源到 sink 节点的多跳路径上成功传输一个数据包 (忽略节点接收、处理数据包的能 耗 )，每一跳所需消耗能量的累积之和 . 命题 1.在自由空间模型 =&#假

21、设下，基站广播的功率等级为 1 r;为得到均匀分布的覆盖半径，基站的 广 播功率以第一级广播功率的 P 倍递增 . 证 明 :设 基 站 以 功 率 等 级 1,2,.， r 广 播 信息 ,对 应 覆 盖 半 径 分 别 为 7?， 2 足 .， 成 的 均 匀 分 布 区 域 ,采 用自由空 间 模 型 五 = 。 # , 则 基 站 的 广 播 功 率 分 别 为 . 当 鐵 能 量 广 播 时 ， 五 产 “ 设 卢 办 ! , 即 基 站 的 广 播 功 率 为 第 1 级 广 播 功 率 的 T2 倍 递增 . 口 命题 2.设 节 点 通 信 的 下 一 跳 节 点 总 是 为

22、其 近 基 站 侧 的 某 邻 居 节 点， 对 于 源 节 点 邱 c,x5 +ljy,+ 1)，如 果 节 点 逻 辑 ID 的 第 2 位 小 于 第 4 位 ， 即 (x5 +l)(y,+l)时， 與 與 2.而 当 (x,+l)=(y,+l)时 ， 以 任 意 基 站 为 汇 聚 节 点 链 路 负 荷 相 当 ， 3 路 由 分 析 本 文 提 出 了 一 种 基 于 虚 拟 网 格 单 元 的 高 可 靠 性 路 由 算 法 (grid-based high reliability routing, 简 称 GHRR),解 决了各个簇头节点如何形成高可靠性的上层数据传输网络的问题

23、 . 3.1 算法描述 本算法以文献 10所描述的 GRAB 算法思想为基础，先建立每个节点的梯度 ,然后数据通过以梯度递减方 向的多个路径向 Sink 节点发送 . 3.1.1 梯度的建立 如前所述，基站通过离散功率等级的方式建立虚拟网格单元，每个单元形成一个簇并选择一个簇头节点， 簇 头与簇内所有成员具有相同的 4 位逻辑 10.对 任意簇头节点 /(， 1,+ 1+1)，当其逻辑 10 第 2 位小于第 4 位， 即 (x,+l) ,+ l)时，梯度为其后两位 的值 ;当 (x,+l)=(y,+l)时，以等概率取节点逻辑 ID 前两位或后两位为梯度 .数据总是沿着梯度递减的方向传 递，而

24、在梯度 增大、相同方向上都没有数据传递，因此避免了路由环的出现，保证了数据向特定基站传送 . 3.1.2 路由算法 为了保证数据传输的鲁棒性，不以单路径或者不相交多路径方式传递数据， 而是以梯度为基础，根据节点 的 通信覆盖半径建立从源到基站的信息传送带，源节点发送的数据通过第 1 跳节点转发进入信息传送带 ,传送 带 的宽度为参与数据转发的每一跳节点数量 .在本算法中，带宽固定为 3, 每个节点在传送数据时自动在包中 绑定 下一跳节点的 ID 号，只有 ID 号相匹配的节点才能接收该数据包，使数据包朝特定方向传递 .下一跳节点 ID 的设 定方法为： 1) 源节点的下一跳节点 .设源节点的

25、ID 为 况 首 先 根 据 命 题 2 选 择 目 的 基 站 . 假 定 ( xs+l) ? ? ; 1 ? 1 2) 信息 传 送带内节点 的 下一跳节点 .为保 证 数据沿梯度 递 减方向传递 ， 当前节 点 ID 前两 位 分别递 减 1 作 为 其 下 一 跳 节 点 ID 的 前 两 位 ,而 下 一 跳 节 点 ID 后 两 位 随 节 点 在 带 内 的 位 置 的 不 同 而 不 同 .由 于 节 点 通 信 覆 盖 半 径 固定 ， 一 个 区 域 的 簇 头 节 点 只 能 与 其 邻 居 区 域 的 簇 头 节 点 通信 ,而 信 息 传 送 带 的 宽 度 限 定

26、为 3,因 此 ， 位 于 信 息 传 送 带 中 间 的 节 点 有 3 个 下 一 跳 节 点 ， 而 处 于 带 边 沿 的 节 点 只 能 与 两 个 下 一 跳 节 点 通 信 ， 如 图 3 所 示 .设 第 /跳 的 3 个节点分别为們 =认 (.,1,.+ 1+1，少 ;+2),说 (知 1,.+ 1,只七 +1),.,办 +1,少厂 1，少儿则信息传送 带的第 ;_+1 跳节 点 集 为 們 厂 1， 少 i+l， M+2)， i u 办 l， Xij+l)， i i (x 厂 l， x;，乂 -以 ).其中， + +1 ? 信息带左边沿节点 ,.乂 的第汗 1 跳 节 点

27、分 别 为 信 息 带 右 边 沿 节 点 的 两 个 第 汗 1 跳 节 点 为 . 而 中 间 节 点 / 的 3 个 下 一 跳节点分别为 ,+,+1 #， ,+1 +可见，并不是所有 3 个下一跳节点都能收 到前一跳的所有 3 节点的广播 的信息 . 当选定了下一跳节点后，信息传送带朝基站方向延伸一跳，如果延伸到 梯度值为 “ 01” 的节点，则说明其下一跳即 为目的基站 . 在整个数据传递过程中，信息传送带不用预先建立，而是在数据传送的同时，根据节点局部信息自主建立， 具有分布式的特征 .不同的源节点建立的信息带不同，且一旦信息传输完毕，信息带即被丢弃 .节点维护一个缓 冲区存放已经

28、转发过的数据包，如果节点收到来自不同上游节点的相同数据包，则从队列中删除 .为减少冲突 , 节点转发数据前等待一个随机时间，避免和邻居节点同时发送数据而引起冲突 . 如 图 3 所 示 ， 信 息 传 送 带 可 能 延 伸 到 目 标 区 域 之 外 .为 避 免 这 种 情 况 的 发 生 ， 当 传 送 带 碰 到 网 格 单 元 位 于 目 标区域边界时反弹一个单元格，使 下 一跳节点集 的 ID 后两位分别递 减 1，即该跳节点的下一跳节点集 的 + 1 向 右 平 移 一 个 单 元 格 , 变 为 奶 + 产 厂 l， x 以 A+l), ,.+1Ax 厂 l,x 以 -l， M

29、),.+1i?(x 厂 l,Xi,乂 -2， 只 -1)， 相应地 ,左边 沿 节 点的 第 z_+l 跳节 点 为 ,+u， 中 间 节 点 的 下 一 跳 节 点 变 为 2 个 : 叫 ， 而 带 右 边 沿 节 点 H, i? 有 3 个 第 汗 1 跳 节 点 此 后 ， 下 一 跳 节 点 集 又 恢 复 为 步 骤 2 ) 所 确 定 的 节 点 集 . 所处虚拟网格单元是否位于目标区域边界， 各 簇 头 节 点 为 探 测 在获得了虚拟 IDh+lj+l)之后，每个簇头节点即广播一条包含 自身虚拟 ID 的探测消息，收到探测消息的节点解析消息中包含的虚 拟 ID 信息 (;+1

30、,3， +1)，获取邻居区域情况，即根据信息包来源判 断自身所处的位置 .若节点未能收到 ID 前两位相同，而后两位分别 递 増 1 的信息包，则本节点位于目标区域左侧的边界 ;若节点未能收到 ID 后两位相同，而前两位分别递增 1 的信息包，则说明本节点位于 右 侧边界区域 ;如果节点未收到前两位相同而后两位分别递减 1，或者 后两位相同而前两位分别递减 1 的信息包，则表明该节点位于下边 界 .如图 1 所示，簇头 2378 所收到的信息包中不含来自 2389 的信息 包，因此 ,2378 位于左侧边界 ;7834 收不到虚拟 ID 为 8934 的信息， 因 为它处于右边界 ;同理 ,2

31、345 未能收到 2334 ， 1245 的信息，则节点 位于 区域下边界 .但是，如果通信质量较差，节点可能收不到某邻居信息 , 因而造成误判 .此时 ,为了提高探测准确度，可以采用其他一些相关 策 略，如 :簇头节点多次发送探测信息，或者簇内每个成员节点都发送一条探测消息 ,并将收到的探测消息发送至 簇头节点，由簇头节点根据上述方法进行判断，从而提高探测准确度 . 3.2.1 可靠性 设节点通信链路丢包率为 e,不考虑节点本身的实效情况 ,并定义八 /)为第 /个节点发送、下一跳第 y 个节 点正确接收的概率，其中， _=1,2,3,12， 13,23,123.例如 ,户 (12,23)表

32、示第 1 个和第 2 个节点发送数据包而下一跳第 2 个和第 3 个节点接收到，其余类推 .同理，定义 F /_； )为第 0 跳第；个节点发送、第 y-1 跳至少 1 个成功接收而 第 J 跳没有节点成功接收，即接收失败的概率，并假定信息传送带第 0 跳的所有 3 个节点都能可靠地收到源节 点 S 发送的数据包并向第 1 跳节点转发，则第 #跳转发失败的概率为 得到如下递推关系式： y=i (6) F i , N) = X P( i ， j) F( J ， N - l ) 7=1,2,3,12,13,23,123 其中户 0,1， 2,3， 12， 13,23， 123，且当 /=1 时 1

33、/矣 3,23， 13,123;当 /=3 时 11， 12， 13,123. (7) (8) 卩 (0,0) = 1 p(. ,j) = , j i = 1, 3 i p(i,0) = e2.e2.e, / = 12,23 z 二 13 2 3 2 ill e .e .e , i = 123 (9) ( l ) 图 4 比 较 了 GHRR、单播、多播路由模式下传输失败率随跳数的变化情况 .可见，对于单路径路由， 15 跳以 后就有 90%的包丢失，即使通信链路的丢包率 e 很小，路由的整体性能也不能得到明显改善 .而在多播路 由模式 下，当 e 为 0.3 时，数据丢包 90%发生在 90

34、 跳以后 ;当 e 为更低的 0.2 时，有 20% 的数据可以传输超 过 200 跳 .可见， 采用多播模式，路由可靠性可以成倍地提高 .图中最下沿的 3 条曲线为本 文提出的高可靠性 路由 GHRR 的性能 曲线，当 e 为 0.3 时，系统在 15 跳时丢包率还不到 5%, 有超过 50% 的数据包可以可靠传输 200 跳以上 ;如果 e 为 0.2 这样的更低值，则有超过 90%的数据包可以传输超过 200 跳 .显然 ,其路由可靠性比 单播、多播模式有了大幅 度的提高 . 3.2.2 链路负荷分析 定义尺 _)为第 0 跳第 z 个节点发送、第 #跳共有 y 个节点正确接收数据包的概

35、率，其中 ,/=1， 2,3,12,13,23, 得到如下递推关系： (20) (21) (22) Fig.4 Failure probability for different number of hops and packet lose rate on a link 图 4 失败率随跳数、链路丢包率变化 图 5 为 GHRR、 单播、多播、 GRAB =3)1()等的链路负荷随跳数的变化关系 .当通信链路丢包率 e 很低 时， 节点通信成功率高，单播、多播路由每一跳只有 1 个节点发送数据，而 GHRR,GRAB 每一跳都有 3 个节点发 送数 据 ，因此 GRAB,GHRR 链路负荷相当

36、，都近似为单播、多播路由负荷的 3 倍 .随着链路丢包率 e 的增加，节点 成功 收到并转发数据包的节点数减少，链路上的数据包相应减少，使得 GHRR,GRAB 的链路负荷呈下降趋势，但 GHRR 具有比 GRAB 更低的链路负荷 .当 e 分别达到并超过 0.35,0.43 以后 ,GHRR 和 GRAB 的链路负荷又逐步 上升，这 是由于随着 e 的逐步增加，端 -端传输失败率增加 (如图 6 所示 )，为了正确地传输一个数据包，源节点可能 需要进 行多次重传 ,数据量增加了 .由图 5 可以进一步看出，在 e 低于 0.41 时 ,GHRR 的链路负荷总是低于 GRAB, 最大可 以低于

37、 60%左右，换句话说 ,GHRR 只牺牲了较小的能耗，而换取了较高的可靠性 . 3.2.3 仿真研究 由以上分析可知，当节点通信链路丢包率低于 0.41 时 ,GHRR 链路负荷比 GRAB 更低 ;在丢包率高于 0.41 时， GHRR 链路负荷并不占优势 .但就整个系统而言，下面的仿真实验将表明 :无论链路丢包率有多大，系统整体 能耗 GHRR 总是明显低于 GRAB. 本 仿 真 实 验 基于 TRUETIME 工 具 12进 行 .TRUETIME 是 一 种 基于 MATLAB/SIMULINK 的 联 合 仿 真 工 具 ， 包 含 计 算机 模 块 (true-time ker

38、nel)、 有 线 网络 模块 (true-time network)、 无 线 网络 模块 (true-time wireless network) 和 电 池 模 块 (true-time battery)， 其 中 ，无 线 网络 模 块带有 802.15.4(ZigBee)协 议 ，为 无 线传 感 器网 络 的综 合 仿真研 究 提供了 良 好的 支 持 .在 以 下实 验 中， 数 据率 均 设定为 l k/s,数 据 包最 小 为 56bit,衰 减 指数 设 定为 2.目 标 区域为 lOOOmxlOOOm 的平面区域，基站 l(sinkl/551)位置坐标为 (0,0),基站

39、 2 扭 1*2/552)位置坐标为 (1000:0)，如图 1 所 示 .两个基站分别以离散功率等级 1 r 广播信息，将目标区域划分为一系列逻辑小区域 . 实验 1.研究链路丢包率 e 对端 -端通信成功率的影响 .目标区域划分为 88 个虚拟网格单元，节点丢包率从 0 0.6 变化，通信成功率变化曲线如图 7 所示 .可以看出，随着 e 的增加 ,GHRR,GRAB 的通信成功率都逐 步下降， 但两者相差不大 . 实验 2.同样基于 88 个虚拟网格单元研究系统能耗情况 .设节点发送功率固定，梯度以节点到基站的跳数 标 示，并以通信成功率作为触发梯度重构的事件，不考虑节点接收、处理数据包

40、以及 节点空闲时的能耗 .图 8 为每 个节点作为源节点发送一个数据包， GHRR 方式与 GRAB 方式下系统总能耗的变化情况相同 .可见，随 着 e 的增 加，系统总能耗逐步下降，而 GHRR 能耗总是低于 GRAB.这是由于系统能耗不仅包括上传数据的链 路负荷，还包 括系统重构梯度时所消耗的能量 .对于 GRAB,重构梯度时每个节点要转发大量控制包，因此消 耗的能量较多 ;而 GHRR 的重构过程由高性能基站以离散功率等级发送初始化消息实现，节点只接收而不转 发数据包，重构梯度 这部分能耗基本上可以忽略不计 . 另一方面， GRAB 在通过泛洪过程建立梯度时，由于受链路丢包率的影响，节点

41、可能未正确接收到来自邻 居 节点转发的控制包，因而建立的通信代价梯度并非最恰当的 .比如 :当某个节点和另一个节点直接通信时， 链路 跳数最少，此时以跳数建立的梯度最优 ;但如果直接通信发生错误，梯度控制包未能直接到达该节点， 而是通过 另一个或几个中间节点中继，则建立的通信代价梯度并不是最优的 .如图 9 所示，节点 1 通过 1 跳 即可到达 4,但 如果此时通信发生错误，则直接导致通信失败，控制包可能经过 2,3 再到达 4,以此建立的节 点 4 的通信代价值多 出了 2 跳，相应地，在后续的数据传输过程中，数据包将可能多经过两跳，使得通信成 网络延迟 . 结合实验 1 及实验 2(图

42、7、图 8)可以看出 ,GHRR 达到了更高的能效而链路可靠性并未受到影响，即 GHRR 牺 牲了更小的能耗，但换取了高可靠性的数据传输 . 实验 3.考察网络平均时间延迟 .网络 平均时间延迟定义为全网所有源 -目的节点对接收数据包和发送数据 包之 间的平均时间差 13， 14.在本实验中，发送端和接收端分别考虑数量级为 1 5 的网络接入时间和数据接收时 间，而不 考虑梯度建立过程中发送控制包建立梯度的时间延迟 .基站分别以 1， 13， 15,17,18 个等级的离散功率广 播信息， 将目标区域划分为 48,88， 116， 142， 165 个虚拟网格单元 .如图 10 所示，随着网络

43、规模的增加，时间延迟增 加，但 GHRR 比 GRAB 时间延迟减少达 22.8%以上，最多可以减少 40.9%,平均减少了 29.3%.显然 ,如果加上梯度 建立过 程中的时间延迟， GHRR 会比 GRAB 时间延迟更低，因为 GHRR 建立梯度不需要节点转发控制包，延迟很 小 ;而 GRAB 需要各个节点以泛洪 +反馈的机制建立路由 15，延迟较大 . Fig.9 Create gradient of nodes (GRAB) 图 9 节 点 梯 度 的 建 立 Fig. 1 0 Comparison of time delay for different number of virtu

44、al grid (or Cluster Head) ( GRAB) 4 结 束 语 本文基于基站的分级离散广播，将目标区域初始化为一系列的虚拟网格，在此基础上提出了 GHRR 路由算 法 . 以节点的 ID 编号作为梯度来控制数据传输方向，路由动态建立，而不必采集网络全局信息，也不必维护路由 表 . 同时，数据通过多个下一跳节点形成的信息传送带直达基站 ,GHRR 在能量的高效性、数据通信的可靠性两 个方面 作了更好的权衡，在 提高数据通信可靠性的前提下减少了系统能耗 . 但算法有些方面还需要进一步改善 :(1)节点发射功率恒定 .本算法中节点采用恒定功率传输数据 ,若根据 其下 一跳的距离远

45、近动态调节发射功率，将有助于在不影响网络最小能耗性能的基础上进一步降低能量开销 , 从而进一 步优化网络的能耗性能 ;(2)算法只考虑了节点通信错误，而对于基站的通信错误没有考虑 .虚拟网格 及节点的逻辑 ID 是在基站广播的数据包都能正确到达的前提下获得的，但在实际应用中 ,通信错误往往很难避 免，下一步我们将 在一定基站通信错误率的情况下对算法作出进一步 的改善 . References: 1 Tan HP, Gabor AF, Seah WKG, Lee PWQ. Performance analysis of data delivery schemes for a multi-sink

46、 wireless sensor network. In: Proc. of the 22nd Infl Conf. on Advanced Information Networking and Applications. 2008. 418-425. http:/ieeexplore.ieee.org/ xpls/abs_all.jsp?arnumber=4482737 2 Cipollone E, Cuomo F, Della Luna S, Monaco U, Vacirca F. Topology characterization and performance analysis of IEEE 802.15.4 multi-sink wireless sensor network. In: Proc. of