《计算机应用研究》|Application Research of Computers

受SINR约束的最小延时数据聚集调度算法

Minimum-latency data aggregation scheduling algorithm with SINR constraints

免费全文下载 (已被下载 次)  
获取PDF全文
作者 刘文彬,李香宝,杨波,文志强
机构 1.湖南财政经济学院 信息管理系,长沙 410205;2.湖南工业大学 计算机与通信学院,湖南 株洲 412008
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2014)11-3409-04
DOI 10.3969/j.issn.1001-3695.2014.11.047
摘要 针对现有的基于物理干扰模型的数据聚集调度近似算法具有延时较高的问题,提出了一种改进的数据聚集调度近似算法。该算法首先构造一个连通支配集作为数据聚集树,使各节点根据数据聚集树分层进行数据调度;然后将整个网络划分为若干个边长相等的正方形区域,使每个区域中最多包含一个支配节点;最后对各个区域进行着色,并从颜色相同的每个正方形区域中任选一个普通节点,使它们能同时将数据汇聚到相应的支配节点。当数据从所有普通节点聚集到相应支配节点后,则将这些正方形区域构成一个大小相同的块,并采用四种颜色对这些块进行着色,使颜色相同的各个块中任选一条通信链路能够同时进行数据传输而不会发生通信冲突和干扰。理论分析表明,该算法的延时上界为K2Δ+8K2R-3R;仿真模拟的结果表明,该算法产生的数据聚集延时低于现有算法。
关键词 数据聚集;最小延时;物理干扰模型;聚集调度算法;通信冲突;信干噪比
基金项目 国家自然科学基金资助项目(61170102)
湖南省教育厅高等学校科学研究资助项目(12C0558,13C094)
湖南省重点学科建设资助项目
本文URL http://www.arocmag.com/article/01-2014-11-047.html
英文标题 Minimum-latency data aggregation scheduling algorithm with SINR constraints
作者英文名 LIU Wen-bin, LI Xiang-bao, YANG Bo, WEN Zhi-qiang
机构英文名 1. Dept. of Information & Management, Hunan University of Finance & Economics, Changsha 410205, China; 2. School of Computer & Communication, Hunan University of Technology, Zhuzhou Hunan 412008, China
英文摘要 This paper presented an improved data aggregation scheduling approximation algorithm, due to the existing data aggregation scheduling algorithms under the physical interference model had high time latency in wireless sensor networks. Firstly, this algorithm constructed a connected dominating set as a data aggregation tree so that every node’s data in network could be scheduled layer by layer. Secondly, it divided the whole network into square cells with the same side length so that each cell contained one dominator at most. Finally, it colored every square cell by using different colors. Therefore, some nodes from the cells with same color could be selected randomly to be scheduled simultaneously. After all dominatees’s data were aggregated to their corresponding dominators, the whole network was divided into large-blocks consisting of same number of square cells, and the four colors were used to color these blocks so that the adjacent blocks had different colors. And then, some communication links were selected randomly from these blocks with same color, which could be scheduled simultaneously without any communication collision and transmission interference. The theoretical analysis shows that the algorithm has a latency bound with K2Δ+8K2R-3R. Simulation results show that this algorithm has lower average latency than previous works.
英文关键词 data aggregation; minimum-latency; physical interference model; aggregation scheduling algorithm; communication collision; SINR
参考文献 查看稿件参考文献
  [1] CHEN Xu-jin, HU Xiao-dong, ZHU Jian-ming. Minimum data aggregation time problem in wireless sensor networks[C] //Lecture Notes in Computer Sciences, Vol 3974. Berlin:Springer, 2005:133-142.
[2] HUANG S C H, WAN Peng-jun, VU C T, et al. Nearly constant approximation for data aggregation scheduling in wireless sensor networks[C] //Proc of IEEE International Conference on Computer Communications. [S. l. ] :IEEE Press, 2007:366-372.
[3] 郭龙江, 任美睿, 李金宝, 等. 降低传感器网络数据聚集延迟的近似调度算法[J] . 黑龙江大学工程学报, 2011, 2(2):80-94.
[4] XU Xiao-hua, LI Xiang-yang, MAO Xu-fei, et al. A delay-efficient algorithm for data aggregation in multihop wireless sensor networks[J] . IEEE Trans on Parallel and Distributed Systems, 2011, 22(1):163-175.
[5] YU Bo, LI Jian-zhong, LI Ying-shu. Distributed data aggregation scheduling in wireless sensor networks[C] //Proc of IEEE International Conference on Computer Communications. [S. l. ] :IEEE Press, 2009:2159-2167.
[6] LI De-ying, ZHU Qing-hua, DU Hong-wei, et al. An improved distributed data aggregation scheduling in wireless sensor networks[J] . Journal of Combinatorial Optimization, 2014, 27(2):221-240.
[7] BOULKABOUL S, DJENOURI D, BADACHE N. FDAP:fast data aggregation protocol in wireless sensor networks[C] //Lecture Notes in Computer Science, Vol 7469. Berlin:Springer 2012:413-423.
[8] 刘文彬, 刘红冰, 付沙, 等. 无线传感网中一种改进的分布式数据聚集调度算法[J] . 计算机应用研究, 2014, 31(1):243-247.
[9] GUPTA P, KUMAR P R. The capacity of wireless networks[J] . IEEE Trans on Information Theory, 2000, 46(2):388-404.
[10] LI Xiang-yang, XU Xia-hua, WANG Shi-guang, et al. Efficient data aggregation in multi-hop wireless sensor networks under physical interference model[C] //Proc of the 6th International Conference on Mobile Ad hoc and Sensor Systems. [S. l. ] :IEEE Press, 2009:353-362.
[11] AN M K, LAM N X, HUYNH D T, et al. Minimum latency data aggregation in the physical interference model[J] . Computer Communications, 2012, 35(18):2175-2186.
[12] XU Xiao-hua, LI Xiang-yang, WANG Peng-jun, et al. Efficient aggregation scheduling in multihop wireless sensor networks with SINR constraints[J] . IEEE Trans on Mobile Computing, 2012, 12(12):2518-2528.
[13] 刘文彬, 杨波, 李香宝, 等. 一种传输能量固定的数据聚集调度近似算法[J] . 计算机应用研究, 2014, 31(3):888-891.
[14] WAN Peng-jun, ALZOUBI K M, FRIEDER O. Distributed construction of connected dominating set in wireless Ad hoc networks[J] . Mobile Networks and Applications, 2004, 9(2):141-149.
收稿日期 2013/9/29
修回日期 2013/11/8
页码 3409-3412,3416
中图分类号 TP393;TP301.6
文献标志码 A