积分商城

最新搜索： STM32F103C8T6 stm32f0 usb源码 随身听 I9300 Authorware 4.0 DfuSe
您现在的位置是：首页 > 技术资料 > 基于连通支配集的无线传感网Top-k查询最优支撑树研究
推荐星级：
  • 1
  • 2
  • 3
  • 4
  • 5

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

更新时间：2019-12-25 03:45:45 大小：2M 上传用户：zhiyao6查看TA发布的资源 标签：无线传感网 下载积分：1分 评价赚积分 （如何评价?） 打赏 收藏 评论(0) 举报

资料介绍

构建底层逻辑树能有效降低集中式top-k查询带来的巨大通信开销,针对现有逻辑树都以固定汇聚节点为根节点,导致其附近节点能耗太大、过早死亡的问题,本文在无固定汇聚节点的网络背景下,基于连通支配集,提出一种能耗均衡的top-k查询最优支撑树构建方法,综合节点能量、度数以及与邻节点通信开销,选取能量代价小的作为支配节点负责查询中间数据处理,在每次查询中,节点基于地理位置ID轮流作为根节点,有效均衡节点的能耗.仿真实验表明,与其他逻辑拓扑树相比,基于最优支撑树的top-k查询具有相近的查询时间,但其平均每轮查询能耗更小,多次查询后各节点能耗达到均衡,有效延长了网络生命周期.


部分文件列表

文件名 大小
基于连通支配集的无线传感网Top-k查询最优支撑树研究.pdf 2M

部分页面预览

（完整内容请下载后查看）
1
Vol． 45 No． 1  
Jan． 2017  
第
期
电
子
学
报
2017  
1
ACTA ELECTRONICA SINICA  
年
月
Top-k  
基于连通支配集的无线传感网  
查询最优支撑树研究  
，
邬海琴 王良民  
(
，
江苏大学计算机科学与通信工程学院 江苏镇江  
212013)  
:
top-k ，  
查询带来的巨大通信开销 针对现有逻辑树都以固定汇聚节  
摘
要
构建底层逻辑树能有效降低集中式  
， 、 ， ， ，  
点为根节点 导致其附近节点能耗太大 过早死亡的问题 本文在无固定汇聚节点的网络背景下 基于连通支配集 提  
top-k  
，
、
，
出一种能耗均衡的  
为支配节点负责查询中间数据处理 在每次查询中 节点基于地理位置  
top-k  
查询最优支撑树构建方法 综合节点能量 度数以及与邻节点通信开销 选取能量代价小的作  
，
，
ID  
， ．  
轮流作为根节点 有效均衡节点的能耗 仿  
，
，
，
查询具有相近的查询时间 但其平均每轮查询能耗更  
真实验表明 与其他逻辑拓扑树相比 基于最优支撑树的  
， ，  
小 多次查询后各节点能耗达到均衡 有效延长了网络生命周期  
．
:
; top-k  
;
;
;
关键词  
中图分类号  
URL: http: / /www． ejournal． org． cn  
无线传感器网络  
查询 连通支配集 能耗均衡 最优支撑树  
0372-2112 ( 2017) 01-0119-09  
DOI: 10． 3969 /j． issn． 0372-2112． 2017． 01． 017  
:
TP393  
:
A
:
文章编号  
文献标识码  
电子学报  
Connected Dominating Set Based Support-Tree for  
Top-k Query in Wireless Sensor Networks  
WU Hai-qin，WANG Liang-min  
( School of Computer Science and Communication Engineering，Jiangsu University，Zhenjiang，Jiangsu 212013，China)  
Abstract: Constructing underlying logic trees can effectively reduce the large communication overhead for centralized  
top-k query． In this paper，an energy-balanced optimal support-tree is proposed to solve the problem of earlier death for nodes  
near sink in sensor networks without fixed sink． This method aggregates node energy，degree and communication overhead，  
and nodes with low energy cost are chosen to be dominating nodes for data processing based on connected dominating set． In  
each query，nodes take turns to be root by location-based ID，which effectively balances the energy cost． The simulation ex-  
periment shows that top-k query based on support-tree outperforms the existing trees by similar query time，but lower average  
energy cost per round and balanced consumption among all sensor nodes after continuous top-k queries，which effectively  
prolong the network lifetime．  
Key words: wireless sensor networks; top-k query; connected dominating set; energy-balanced; optimal support-tree  
) ， 、 ，  
最小 监测值 如温度 污染物指数等 从而起到森林预  
1
引言  
、 ．  
警 判断污染程度较高地区的作用 由于无线传感器节  
( Wireless Sensor Network，WSN)  
无线传感器网络  
是
，
点通常部署在无人看守的恶劣环境中 因此对能量严  
，
由部署在监测区域内的大量传感器节点 通过无线通  
， 、  
格受限的传感器网络 降低网络能耗 延长网络寿命成  
ad hoc  
，
网络 节点不具有移动性且  
信方式形成的特殊  
top-k  
．
为
查询的关键问题  
Top-k  
，
、
．
，WSN  
能量较少 计算 通信能力较弱 近年来  
在多个领  
动物保护以及目  
查询作为传感网查询应用的重要  
，
查询主要从两方面减少网络能耗 一是构建  
［1］  
，
、
域得到广泛应用 如环境污染监测  
，
底层逻辑拓扑树 主要以数据查询节点  
( sink)  
作为根节  
［2，3］  
， top-k  
等 而  
标跟踪  
， — ，  
点 在节点间建立父亲 孩子关系 先由  
sink  
广播用户  
， k (  
内容 用户可根据自身需要查询监测区前 个最大 或  
，
查询至叶子节点 各叶子节点将自身感知值发送至其  
: 2015-05-29;  
: 2015-08-01;  
:
责任编辑 孙瑶  
收稿日期  
修回日期  
:
基金项目 国家自然科学基金  
( No． 61272074) ;  
( No． U1405255) ;  
( No． GY2013030)  
镇江市工业支撑计划  
国家自然科学基金海峡基金重点项目  
120  
2017  
年
电
子
学
报
， k，  
父节点汇聚 若数据量大于 则先在本地进行  
top-k  
，
准确性 能耗也远小于  
FILA．  
DST  
的构建主要依赖  
查
其中  
， ，  
询 再将查询结果发送给父节点 直至  
sink．  
， ( )  
于最小连通支配集 选择邻居节点多 度数大 的作为  
与集中式查  
sink  
， ，  
询相比 大大减少了通信开销 但也由此带来  
，
支配节点 使中间传输数据的非叶子节点的个数达到  
附近  
， ， “  
节点负载过多 能耗太大过早死亡的问题 这些 瓶颈  
．
最少  
［17］  
” ;  
节点 决定了网络寿命 另一方面是研究高效的  
top-k  
Cho  
( POT)  
等提出了利用空间相关的感知数据建立偏  
top-k  
， ［4］  
查询算法 如文献 提出的基于  
filter  
，
的算法 其主要  
，
查询 其主要思想是在网络中选  
序树  
进行  
top-k  
“ ”( )  
择 热点 较高感知值的节点 建立逻辑拓扑来减少不  
思想是将下一轮最有可能成为  
结果的数据发送给  
sink， ，  
减少无效的数据传输 从而降低通信开销  
．
．
必要的数据更新 此方法适用于高度非均匀的数据分  
， ，  
延长网络寿命 不仅要减少网络的整体能耗 更应  
， ，  
．
查询的一个  
( HGIT)  
将
布 但当热点较少或没有热点时 其性能会迅速降低  
． ，  
使网络中各节点能耗达到均衡 在查询过程中 能量消  
，
最近 层次索引树的构建也成为  
top-k  
［18］  
． Tang  
“ ”，  
耗快的节点将成为整个网络的 瓶颈节点 节点能耗  
研究重点  
等构建的层次网格索引树  
n
n
， ，  
不均会导致某些节点提前死亡 因此 构建能耗均衡的  
2 × 2  
，
n + 1  
监测区域划分为  
个网格单元 建立  
层索引  
WSN  
等人也将 分为两层  
［19］  
，
树 简化了逻辑拓扑  
; Wang  
．
逻辑树对延长网络寿命起着至关重要的作用  
: ，  
拓扑 簇头节点层和普通节点层 有效降低了数据查询  
，
本文在连通支配集理论基础上 提出了能耗均衡  
，
的最优支撑树构建方法 其主要特点在于  
:
．
更新代价  
sink  
，
为根节点 每轮查询根  
( 1)  
、
综合考虑了节点度数 能量和通信代价三个因  
以上逻辑树都以固定  
， ，  
节点唯一 且簇头选取时未考虑节点初始能量 当查询  
，
素选择低能耗连通支配节点 负责其被支配节点的数  
、k ， sink  
次数 值增大时 会导致 附近节点能耗不均而死  
，
据查询处理和转发 而高能耗节点作为叶子节点参与  
， 1  
亡 表 比较了不同逻辑拓扑树的构建方法  
．
， ， “ ”  
较少通信 有效均衡了节点能耗 避免 瓶颈节点 过早  
1
Top-k  
查询底层逻辑树构建方法对比  
表
．
死亡  
( 2)  
所选择的低能耗连通支配节点虽不是最小连  
平均每轮 是否考虑  
查询能耗 节点能量  
方法  
构建特点  
网络环境  
， ，  
通支配集 增加了单轮查询能耗 但通过协调节点间的  
， ，  
通信量 延长了单个节点寿命 最终延长整个网络寿命  
，
SPT  
DST  
sink  
sink  
sink  
sink  
基于最短路径  
基于最小连通支配集  
基于空间相关性  
基于层次索引  
唯一  
唯一  
唯一  
唯一  
较高  
较高  
较低  
较低  
否
否
否
否
．
从而降低了平均每轮查询的能耗  
( 3) top-k  
ID  
轮流  
每轮  
查询由节点基于地理位置  
POT  
HGIT  
sink，  
，
打破了根节点唯一的传统 有效延长了网络  
作为  
．
寿命  
， 、  
针对这些问题 本文综合考虑节点能量 度数以及  
2
相关工作  
， ，  
通信代价 并以此定义最优函数选取支配节点 构建最  
Top-k  
查询在多种数据环境中的应用已有广泛研  
( Optimal Support-Tree，OST) ． ID  
树中的节点按  
sink ，  
优支撑树  
，
号轮流作为根节点 即每次  
［5］  
［6］  
，
究 如多媒体数据库  
，
关系数据库 以及传感器网  
top-k  
查询的  
均不同 此  
［7，8］  
．
等 在分布式传感网环境中  
，top-k  
络
查询主要分为  
sink  
方法打破了传统传感器网络  
固定带来的其附近节  
［9］  
:
两类 一类称为多维  
top-k  
， k  
旨在找到 个排名最  
查询  
， ，  
点过早死亡的弊端 有效均衡了节点的能耗 从而延长  
， ，  
高的数据点 每个数据点有多个属性值 根据用户查询  
．
整个网络寿命  
f ; k ，  
函数 计算排名 另一类则是找出 个最高感知值 假  
3
网络模型及相关定义  
，
设每个传感器节点每次只产生一个感知值 又称单一  
top-k  
．
n
查询  
假设无线传感器网络中 个节点随机分布在二维  
， ID  
平面上 每个传感器节点按其地理位置形成唯一的  
top-k  
，
查询 目前已有一些底层逻辑树构  
对于单一  
［10 ～ 12］  
［13 ～ 16］  
［4］  
top-k  
，Wu  
， i = 1，2，…，n，ID  
号 即  
，
号相邻的节点地理位置也相邻  
建算法  
和
查询算法  
等人提出的  
FILA  
SPT  
，SPT sink  
基于范围的  
算法以  
为根节点 其余节点均有到  
了集中式查询带来的巨大通信开销 但其查询结果不  
作为逻辑树  
以
无线传感器网络的物理拓扑结构可抽象为一个简单的  
，
sink  
，
G( V，E) ， V ，E  
其中 表示节点集合 表示边  
的最短路径 大大减少  
无向连通图  
u、v  
，
，
d( u，v) r，( u，v)  
之间存在边当且仅当 ≤  
集合 节点  
E( u，v V) u、v  
即节点  
．
， 2  
是相邻的 表 给出了本  
准确  
∈
其中  
∈
［11］  
Balijeet  
DST  
top-k  
．
文中用到的相关符号和参数说明  
等人提出了基于  
的
查询算法  
EXTOK，  
通过为每个节点设置过滤阈值来决定其下一  
1
( MIS) :  
G( V，  
给定图  
定义  
E) ， M  
独立集和极大独立集  
sink  
．
发送更新值 该算法保证了  
top-k  
V
u，v M，  
∈ 都有  
( u，v) E， M  
则称  
轮是否向  
查询的  
若
且对于  

相关下载

全部评论(0)

暂无评论
评论赚积分>>

上传资源 上传优质资源有赏金

热门标签

更多>>

最新上传

  • 打赏
  • 30日榜单

热门下载

资料专题

推荐下载

本站上的所有资源均为源于网上收集或者由用户自行上传，仅供学习和研究使用，无任何商业目的，版权归原作如有侵权，请 来信指出，本站将立即改正。

ICP许可证号：京ICP证070360号     21IC电子网 2000- 版权所有

京ICP备11013301号

京公网安备 11010802024343号