Multi-Radio无线传感器网络中基于缓存和信道切换的数据查询算法的研究  

Data Query Based on Data Cache and Channel Switch in Multi-Radio Wireless Sensor Networks

作　　者：张艳卿[1,2] 李金宝[1,2] 郭龙江[1,2] 朱敬华 

机构地区：[1]黑龙江大学计算机科学技术学院,哈尔滨150080 [2]黑龙江省数据库与并行计算重点实验室,哈尔滨150080

出　　处：《计算机学报》2012年第11期2403-2414,共12页Chinese Journal of Computers

基　　金：国家自然科学基金(61070193;61100048);黑龙江省杰出青年基金(JC201104);黑龙江省科技攻关项目(GC09A109);黑龙江省高校科技创新团队建设计划(2011PYTD002);教育部新世纪优秀人才支持计划资助(NCET-11-0955);黑龙江省教育厅新世纪优秀人才支持计划(1252-NCET-011)资助~~

摘　　要：针对Multi-Radio Multi-Channel传感器网络中链路服务质量和信道冲突等问题,提出并证明了基于缓存和信道切换的数据查询问题是一个NP完全问题.根据数据流守恒和链路-信道等约束条件,建立线性规划方程,得到该问题的最优解模型,并提出了一个多项式时间的近似算法——贪心新覆盖数据算法.该算法采用动态规划策略最小化缓存节点将单位数据包传输到查询节点所需要的路径时延,再贪心选择其具有最小路径时延的缓存节点,收集其新覆盖数据.理论分析和实验结果表明,提出的方案能有效地减少数据收集时延,提高数据查询效率.Due to the nature of multi-radio multi-channel wireless sensor networks, such as the quality of service of the links, channel conflict etc. , we investigated the problem of data query based on data cache and channel switch, and proved it to be an NP-complete problem. Firstly, we constructed a LP equation based on the data flow conservation and link-channel constraint etc. to formulate the problem, then designed a polynomial approximate algorithm. The algorithm used dynamic programming strategy to minimize the delay of unit data packet transmission from cache nodes to the query node, greedily chose a cache node with the smallest delay of unit data packet transmission, and collected the new covered data packets. Theoretical analysis and experimental results indicate that the proposed algorithm can reduce the communicate delay and improve the efficiency of query effectively.

关 键 词：Multi—Radio Multi—Channel网络 数据缓存 数据查询 信道切换 信道冲突 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]