基于连通支配集的无线传感网Top-k查询最优支撑树研究

mytomorrow

基于连通支配集的无线传感网Top-k查询最优支撑树研究

& h* b/ C2 t# I8 ?1 S' i摘要:构建底层逻辑树能有效降低集中式top-k查询带来的巨大通信开销,针对现有逻辑树都以固定汇聚节点为根节点,导致其附近节点能耗太大、过早死亡的问题,本文在无固定汇聚节点的网络背景下,基于连通支配集,提出一种能耗均衡的 top-k查询最优支撑树构建方法,综合节点能量、度数以及与邻节点通信开销,选取能量代价小的作为支配节点负责查询中间数据处理,在每次查询中,节点基于地理位置ID轮流作为根节点,有效均衡节点的能耗.仿真实验表明,与其他逻辑拓扑树相比,基于最优支撑树的top-k查询具有相近的查询时间,但其平均每轮查询能耗更小,多次查询后各节点能耗达到均衡,有效延长了网络生命周期.
% O# X) S; x5 o2 w; R$ e关键词:无线传感器网络;top-h查询;连通支配集;能耗均衡;最优支撑树
; `) Y/ g- q6 I3 N
  M# L# U; x& t! A+ }) I( J# B
1引言
无线传感器网络( Wireless Sensor Network , WSN)是由部署在监测区域内的大量传感器节点,通过无线通信方式形成的特殊ad hoc 网络,节点不具有移动性且能量较少,计算、通信能力较弱.近年来,WSN在多个领域得到广泛应用,如环境污染监测"、动物保护以及目标跟踪[23]等,而top-k查询作为传感网查询应用的重要内容,用户可根据自身需要查询监测区前k个最大(或最小)监测值,如温度、污染物指数等,从而起到森林预警、判断污染程度较高地区的作用.由于无线传感器节点通常部署在无人看守的恶劣环境中,因此对能量严格受限的传感器网络,降低网络能耗、延长网络寿命成为top-k查询的关键问题.
Top-k查询主要从两方面减少网络能耗,一是构建底层逻辑拓扑树,主要以数据查询节点( sink)作为根节点,在节点间建立父亲一孩子关系,先由 sink广播用户查询至叶子节点,各叶子节点将自身感知值发送至其父节点汇聚,若数据量大于k,则先在本地进行top-h查询,再将查询结果发送给父节点,直至sink.与集中式查询相比,大大减少了通信开销,但也由此带来sink附近节点负载过多,能耗太大过早死亡的问题,这些“瓶颈节点”决定了网络寿命;另一方面是研究高效的 top-k查询算法,如文献[4]提出的基于filter 的算法,其主要思想是将下一轮最有可能成为top-h结果的数据发送给sink ,减少无效的数据传输,从而降低通信开销.
; X2 ~% |6 F: U$ G+ p延长网络寿命,不仅要减少网络的整体能耗,更应使网络中各节点能耗达到均衡.在查询过程中,能量消耗快的节点将成为整个网络的“瓶颈节点”,节点能耗不均会导致某些节点提前死亡,因此,构建能耗均衡的逻辑树对延长网络寿命起着至关重要的作用.
: Y% {" s0 @( O+ b1 Q, j本文在连通支配集理论基础上,提出了能耗均衡的最优支撑树构建方法,其主要特点在于:
(1)综合考虑了节点度数﹑能量和通信代价三个因素选择低能耗连通支配节点,负责其被支配节点的数据查询处理和转发,而高能耗节点作为叶子节点参与较少通信,有效均衡了节点能耗,避免“瓶颈节点”过早死亡.

$ B$ s* @, O; h' Y4 i4 j+ T" L

游客，如果您要查看本帖隐藏内容请回复

1 x8 @$ y0 l: k1 d, \* L6 c
+ h$ O- ?* }* n# M: E! y; Y
, s5 r& |8 j- A5 [% e
0 V9 L+ x/ J9 E% c& p+ L

ExxNEN

基于连通支配集的无线传感网Top-k查询最优支撑树研究