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

mytomorrow

基于连通支配集的无线传感网Top-k查询最优支撑树研究
+ T2 V# w# O) g% }- [3 L' l/ {
* r! G+ o4 I# s# M! S5 S- G摘要:构建底层逻辑树能有效降低集中式top-k查询带来的巨大通信开销,针对现有逻辑树都以固定汇聚节点为根节点,导致其附近节点能耗太大、过早死亡的问题,本文在无固定汇聚节点的网络背景下,基于连通支配集,提出一种能耗均衡的 top-k查询最优支撑树构建方法,综合节点能量、度数以及与邻节点通信开销,选取能量代价小的作为支配节点负责查询中间数据处理,在每次查询中,节点基于地理位置ID轮流作为根节点,有效均衡节点的能耗.仿真实验表明,与其他逻辑拓扑树相比,基于最优支撑树的top-k查询具有相近的查询时间,但其平均每轮查询能耗更小,多次查询后各节点能耗达到均衡,有效延长了网络生命周期.
; H* Z# e0 N: ]关键词:无线传感器网络;top-h查询;连通支配集;能耗均衡;最优支撑树
. H, y; D$ W2 I) u  j4 [& W

- F9 h( q/ _. s1 Y1引言
) a$ i' |1 T. S  L* X无线传感器网络( Wireless Sensor Network , WSN)是由部署在监测区域内的大量传感器节点,通过无线通信方式形成的特殊ad hoc 网络,节点不具有移动性且能量较少,计算、通信能力较弱.近年来,WSN在多个领域得到广泛应用,如环境污染监测"、动物保护以及目标跟踪[23]等,而top-k查询作为传感网查询应用的重要内容,用户可根据自身需要查询监测区前k个最大(或最小)监测值,如温度、污染物指数等,从而起到森林预警、判断污染程度较高地区的作用.由于无线传感器节点通常部署在无人看守的恶劣环境中,因此对能量严格受限的传感器网络,降低网络能耗、延长网络寿命成为top-k查询的关键问题.
+ k2 z' Y* K2 OTop-k查询主要从两方面减少网络能耗,一是构建底层逻辑拓扑树,主要以数据查询节点( sink)作为根节点,在节点间建立父亲一孩子关系,先由 sink广播用户查询至叶子节点,各叶子节点将自身感知值发送至其父节点汇聚,若数据量大于k,则先在本地进行top-h查询,再将查询结果发送给父节点,直至sink.与集中式查询相比,大大减少了通信开销,但也由此带来sink附近节点负载过多,能耗太大过早死亡的问题,这些“瓶颈节点”决定了网络寿命;另一方面是研究高效的 top-k查询算法,如文献[4]提出的基于filter 的算法,其主要思想是将下一轮最有可能成为top-h结果的数据发送给sink ,减少无效的数据传输,从而降低通信开销.
# f- p+ x, H/ S4 {延长网络寿命,不仅要减少网络的整体能耗,更应使网络中各节点能耗达到均衡.在查询过程中,能量消耗快的节点将成为整个网络的“瓶颈节点”,节点能耗不均会导致某些节点提前死亡,因此,构建能耗均衡的逻辑树对延长网络寿命起着至关重要的作用.
& f) Y1 H( Y3 C8 H. v7 u本文在连通支配集理论基础上,提出了能耗均衡的最优支撑树构建方法,其主要特点在于:
. v3 Z$ [8 ~) v, r% x5 d8 o8 m(1)综合考虑了节点度数﹑能量和通信代价三个因素选择低能耗连通支配节点,负责其被支配节点的数据查询处理和转发,而高能耗节点作为叶子节点参与较少通信,有效均衡了节点能耗,避免“瓶颈节点”过早死亡.

; i. g; Z9 z" \  e# |

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

# h1 J; u. g( H, H8 g/ J' G
& J9 R/ s3 K5 [
. o7 m, `7 y# T3 y3 [

ExxNEN

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