无线传感器网络基于数据汇聚的路由
- 格式：pdf
- 大小：229.76 KB
- 文档页数：4
%!
!""#$%! 计算机工程与应用
须经过的中间节点的集合。那么一定存在一棵包含节点集合 ) 和集合 , 以及节点 * 的一个生成树 !(， !(即为传感器网络的最 小传输代价生成树。 证明 传感区域内的所有节点都要将传感数据传输给汇聚 下 点， 因此最小传输代价生成树必然包括节点集合 ) 和节点 * 。 面证明必然包括节点集合 ,。 用反证法，假设最小传输代价生成树中总存在一个节点 但是 %") ， %， %!" ， %#+ ， %#*， %",。即 % 不在从节点 + 到 * 的 最短路径所必须经过的节点中，那么数据包从 + 到 % ，再从 % 传输到 *， 所需要的传输代价必然大于最短路径的传输代价。 这
无线传感器网络基于数据汇聚的路由
彭
!
刚%
曹元大 %
钟伟军 %
孙利民 !
% （北京理工大学计算机系， 北京 %"""-% ） （中科院软件所多媒体和网络研究中心， 北京 %"""-" ）
3456/7： 890::60:;%!+$<=5
摘 要 提出了一种针对无线传感器网络的路由协议， 该路由采用最小传输成本生成树的数据汇聚机制。 具体方法是首
&-)
微机电系统制造技术的飞速发展， 具有感知、 计算存储和通信 能力的微型传感器开始出现在军事、 工业、 农业和宇航各个领 域。无线传感器节点是集传感器执行器、 控制器和通信装置于 一体的嵌入式设备。 由这些微型传感器构成的无线传感器网络 能够实时监测、 感知和采集网络分布区域内的各种监测对象信 息， 并对这些信息进行处理， 传送给需要这些信息的用户 &%’()。 传感器网络在军事侦察、 环境信息检测、 农业生产、 医疗健 康监护、 建筑与家居、 工业生产控制以及商业等领域有着广阔
#) 。 的应用前景 &*，
， 它
采用面向应用的网内数据处理。 由于无线传输一个字节所消耗 的电能比计算一个字节所消耗的电能要高几个数量级， 因此采 用了数据汇聚技术的定向扩散可以节省大量的电能。
!
路由算法
传感器网络中的数据大多都是从多个源节点传递到一个
传感器网络和传统网络相比， 有着独有的特点。无线传感 器网络面临的主要技术挑战是在资源受限的条件下完成感知、 通信和控制功能。 这些限制主要包括： 有限的能量供应、 有限的 计算能力、 有限的存储空间和有限的通信能力。 因此， 以往针对传统网络所提出的一些路由协议对传感器 网络并不适用， 需要采用新的的技术。 为了尽量延长资源受限的传感器网络的生命期， 一个十分 有用的技术是在传感器网络的路由中采用数据汇聚机制 消除冗余， 减小数据传输量， 从而节省电能。
文章编号 %""!4-((%4 （!""# ） %!4""%!4"(
文献标识码 ?
!"#$%&’ "( )*$* +’’,-’*$%"& (", .%,-/-00 1-&0", 2-$3",40
5-&’ 6*&’7 8*" 9#*&:*7 ;<"&’ .-%=#&7 1#& >%?%&@ （C986DE590E =F G=58HE9D I</90<9 602 30:/099D/0: ， J9/K/0: L0.E/EHE9 =F @9<M0=7=:N ， J9/K/0: %"""-%） ! （L0.E/EHE9 =F I=FEO6D9 ， EM9 GM/09.9 ?<6295N =F I</90<9.， J9/K/0: %"""-"）
01/,2345:#? 6724/&81:@""? 9,3,5:"
每 个 接 收 到 该 查 询 消 息 - 的 节 点 首 先 保 存 该 消 息 -， 并 将消息的发送者作为父节点。然后判断自己的位置 A8?&/&81 是 否 处 于 传 感 区 域 -,./ 之 内 ， 如 果 不 在 -,./ 之 内 ， 则将该消息 然后继续将该消息 - 往其邻 中的 9,3,5 值增一并记录该消息， 居节点广播。 则比较其中 如果节点接收到多个节点发送的任务消息 -， 的 9,3,5 值，如果新接收的要小于该 9,3,5 就用最新 的 发 送 者 作为其父节点。丢弃掉大于或等于已有的 9,3,5 值的消息。 一 旦 某 个 节 点 判 断 出 该 节 点 的 位 置 在 传 感 区 域 -,./ 之 并将该项的值设 内， 则 在 此 消 息 中 添 加 一 个 属 性 9,3,501B2,4 ， 为 "， 即 9,3,501B2,4:" ， 从而形成了一个新的任务 消 息 . ； 然后 继续向邻居广播。 此后， 将以该节点作为根节点， 构造一个包含 于 -,./ 区域之内所有传感节点的最小生成树。 在传感区域之内的节 点 如 果 接 收 到 . 消 息 ， 则 记 录 其 发 送者， 作为该节点的父节点， 然后 9,3,501B2,4 的值加一。一旦
%
引言
随着传感器技术、 嵌入式计算技术、 通信技术和半导体与
传统网络的路由技术是一种以地址为中心的路由技术， 它 是在两个可寻址的节点对之间寻找最短路由。 而传感器网络的 路由是一种以数据为中心的路由， 目的是寻找多个源节点到一 个汇聚节点的路径， 采用网内数据汇聚， 实现冗余数据的合并。 定向扩散就是一种十分有效的以数据为中心的路由技术
息 - 给网络内的所有节点，这个查询消息包括一个 传 感 类 型 传 感 范 围 -,./、 间 隔 时 间 01/,2345、 持 续 时 间 6724/&81 和 )*+, 、 节点级别 9,3,5。初始的任务消息 - 的一个事例如下： )*+,:湿度 -,./:;!" ， #" ， <" ， =">
($%
最小传输代价生成树
传感器网络内的所有节点和能够实现直接通信的节点对
就构成了一个连通图。 设 图 ! 是 由 " 和 # 两 个 集 合 所 组 成 的 二 元 组 ， 记 为 !$ （" ， ，其中 " 是节点的非空有限集合， #） # 是 " 中节点对的集 合，是能够直接通信的节点对的集合。当然在传感器网络中， 否则不能连接成为网络。 "， # 都不会为空集， ! 中的每一条边应该都是有方向的，即 ! 是一个有向图， 节点对 （% ， 表示从 节 点 % 可 以 直 访 问 到 节 点 &， 在一般情况 &） 表示是一种对称的 下， 节 点 & 应 该 也 可 以 直 接 访 问 到 节 点 %， 访问模式。因此不失一般性， 可 认 为 ! 是 无 向 图 。# 中 的 每 都有一个权值 ’ （% ， ， 在传感器网络中， （% ， 假设 条边 （% ， &） &） ’ &） 都为 % 。 （" ( ， ， 定 义 !( 是 ! 的 一 个 连 通 子 图 ， !($ #( ） " (至 少 包 括 了汇聚点和传感区域内的所有节点， 称 !( 为 ! 的传输生成树。 在 ! 的所有传输生成树中，耗费最小的生成树称为 ! 的最小 传输代价生成树。 通过最小传输代价生成树 !( ，传感区域 内 的 所 有 节 点 将 传感数据发送给汇聚点时， 节点之间传输的次数最少， 即传输 代价最小。 （" ， 是一个无向连通带 权 图 ， 设传感区域内 命题 设 !$ #） 的节点集合为 ) ， 设 * 为汇聚点， ) 为 " 的一个真子集。 + 为集合 ) 中距离 * 点距离最近的节点。 , 为从 + 到 * 的 最 短 路 径 所 必
%
+A0$,*B$： ? D=HE/0: 8D=E=<=7 F=D O/D979.. .90.=D 09EO=D1. O6. 8D=8=.92$@M9 8D=E=<=7 H.92 6 26E6 6::D9:6E/=0 .<M959 =F 5/0/5H5 ED60.5/../=0 <=.E .8600/0: ED99$L0 EM/. 8D=E=<=7， EM9 0=29 /0 .90./0: D9:/=0 OM/<M /. 096D9.E EM9 ./01 6<E. 6. EM9 6::D9:6E/=0 8=/0E$?77 =EM9D 0=29. /0 .90./0: D9:/=0 .902 EM9/D 26E6 E= EM/. 6::D9:6E/=0 0=29， EM90 .902. EM9 6::D9:6P E/=0 /0F=D56E/=0 E= EM9 ./01 67=0: EM9 .M=DE9.E 86EM$3Q89D/590E67 D9.H7E. .M=O EM6E EM9 26E6 D=HE/0: 8D=E=<=7 <60 <6H.9 D=H:M7N #">’-"> F9O9D ED60.5/../=0. 602 6 R/E .M=DE9D ED60.5/../=0 2976N$ C-D3",:0： O/D979.. .90.=D 09EO=D1.， 26E6 6::D9:6E/=0 ， 26E64<90ED/< D=HE/0: ， 5/0/5H5 ED60.5/../=0 <=.E .8600/0: ED99
要的跳数较多， 因此数据包数量较多。 随着传输半径的增大， 传 输所需的跳数减少， 传输所需要的数据包数量大大减少。 无汇聚需要传输的数据包的数量最多，随机汇聚次之， 最 小传输代价生成树的汇聚策略数据包的数量最少， 从而消耗的 能量最小。可见， 有数据汇聚的策略由于将多个数据包汇聚成 一个数据包， 大大减少了传输的数据包的数量， 数据包数量比 即节省能量 #"97/"9。 无汇聚情况减少了 #"97/"9，
