基于二次独立集的数据融合调度算法

doi:10.3969/j.issn.1000-436x.2014.01.008

Journal on Communications ›› 2014, Vol. 35 ›› Issue (1): 62-71.doi: 10.3969/j.issn.1000-436x.2014.01.008

• academic paper • Previous Articles Next Articles

Data aggregation scheduling algorithm based on twice maximum independent set

Jian XU^1,²,Geng YANG^1,²,Zheng-yu CHEN^2,³,Hai-yong WANG²,Zhen YANG³

¹ Key Laboratory of Broad Band Wireless Communication ＆ Sensor Networks Technology of Ministry of Education,Nanjing University of Posts ＆ Telecommunications,Nanjing 210003,China
² College of Computer Science ＆ Technology,Nanjing University of Posts ＆ Telecommunications,Nanjing 210003,China
³ School of Information and Technology,Jinling Institute of Technology,Nanjing 211169,China

Online:2014-01-25 Published:2017-06-17
Supported by:
The National Basic Research Program of China (973 Program);The National Science Foundation of China;The Natural Science Foundation of Jiangsu Province;The Natural Science Foundation of Jiangsu Province;The Natural Science Foundation of Jiangsu Province;The Research Fund for the Doctoral Program of Higher Education of China;The Research Fund for the Doctoral Program of Higher Education of China;The Innovation Project for Postgraduate Cultivation of Jiangsu Province;The Innovation Project for Postgraduate Cultivation of Jiangsu Province;The Innovation Project for Postgraduate Cultivation of Jiangsu Province;The Innovation Project for Postgraduate Cultivation of Jiangsu Province

Abstract

Abstract:

The main task in designing a data aggregation schedule was to get a good trade-off between QoS and weighted fairness guarantee.In order to address this problem,a novel data aggregation scheduling algorithm,MISS,was proposed,which could produce a collision-free TDMA schedule for data aggregation based on twice Maximum Independent Set (MIS).In the first phase,a tree structure based on MIS was constructed,and then it was adjusted according to the energy consumption forecast of each node,forming the balanced data aggregation tree.In the second phase,the approximate maximum weighted Independent set (WMIS) was utilized of all selected links to allocate time slots for each communication link.The results of simulation demonstrate that MISS not only improves the aggregation delay and lifetime of the network,but also gives weighted fairness guarantee.

Key words: wireless sensor networks, data aggregation, time division multiple access, scheduling algorithm, maximum independent set, aggregation tree

Jian XU,Geng YANG,Zheng-yu CHEN,Hai-yong WANG,Zhen YANG. Data aggregation scheduling algorithm based on twice maximum independent set[J]. Journal on Communications, 2014, 35(1): 62-71.

Figures/Tables 14

References 15

[1]	ERGEN S C , VARAIYA P . TDMA scheduling algorithms for wireless sensor networks[J]. Wireless Networks, 2010,(16): 985-997.
[2]	ERGEN S C , VARAIYA P . PEDAMACS:Power efficient and delay aware medium access protocol for sensor networks[J]. IEEE Transactions on Mobile Computing, 2007,5(7): 920-930.
[3]	FASOLO E , ROSSI M , WIDMER J ,et al. In-network aggregation techniques for wireless sensor networks:a survey[J]. IEEE Transactions on Wireless communication, 2007,14(2): 70-87.
[4]	LUO D J , ZHU X J , WU X B . Maximizing lifetime for the shortest path aggregation tree in wireless sensor networks[A]. Proceedings of the IEEE INFOCOM[C]. Shanghai,China, 2011. 1566-1574.
[5]	GHOSH A , INCEL O D , ANILKUMAR V S . Multi-channel scheduling and spanning trees:throughput-delay tradeoff for fast data collection in sensor networks[J]. IEEE/ACM Transactions on Networking, 2011,19(6): 1731-1744.
[6]	HUANG S C , WAN P J , VU C T ,et al. Nearly constant approximation for data aggregation scheduling in wireless sensor networks[A]. Proceedings of the IEEE INFOCOM[C]. Alaska,USA, 2007. 366-372.
[7]	YU B , LI J Z , LI Y S . Distributed data aggregation scheduling in wireless sensor networks[A]. Proceedings of the IEEE INFOCOM[C]. Rio,Brazil, 2009. 2159-2167.
[8]	XU X H , LI X Y , MAO X F . A delay-efficient algorithm for data aggregation in multi-hop wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2011,22(1): 163-175.
[9]	JOO C H , CHOI J G , SHROFF N B . Delay performance of scheduling with data aggregation in wireless sensor networks[A]. Proceedings of the IEEE INFOCOM[C]. San Diego,USA, 2010. 1-10.
[10]	GUPTA P , KUMAR P R . The capacity of wireless networks[J]. IEEE Transactions on Information Theory, 2000,46(2): 388-404.
[11]	BALJEET M , IOANIS N , MARIO A N . Aggregation convergecast scheduling in wireless sensor networks[J]. Wireless Networks, 2011,17: 319-335.
[12]	WU Y W , LI X Y , LIU Y H ,et al. Energy-efficient wake-up scheduling for data collection and aggregation[J]. IEEE Transactions on Parallel and Distributed Systems, 2010,21(2): 275-287.
[13]	WU Y , FAHMY S , SHROFF N B . On the construction of a maximum lifetime data gathering tree in sensor networks:np-completeness and approximation algorithm[A]. Proceedings of the IEEE INFOCOM[C]. Phoenix,USA, 2008. 1013-1021.
[14]	HAN B , FU H H , LIN L D ,et al. Efficient construction of connected dominating set in wireless ad hoc networks[A]. Proceedings of the IEEE International Conference on Mobile Ad-hoc and Sensor System[C]. Florida,USA, 2004. 570-572.
[15]	CHALERMEK I , RAMESH G , DEBORAH E . Directed diffusion:a scalable and robust communication paradigm for sensor networks[A]. Proceedings of the Sixth Annual International Conference on Mobile Computing and Networking (MobiCOM '00)[C]. Boston,USA, 2000.

Metrics

Recommended 0

No Suggested Reading articles found!

变量名	表示内容	取值
N	节点个数	200～1 200
L	仿真区域	200
r	节点传输半径/m	25
r_I	节点干扰半径/m	25
EN	节点初始能量	1 000
P_t	发送一次消耗的能量	2
P_r	接收一次消耗的能量	1
w_i	节点i的权重	rand(0.0,10.0)

Data aggregation scheduling algorithm based on twice maximum independent set

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 14

References 15

Related Articles 15

Metrics

Recommended 0

[1]	Baiji HU, Xiaojuan ZHANG, Yuancheng LI, Rongxin LAI. Multi-function supported privacy protection data aggregation scheme for V2G network [J]. Journal on Communications, 2023, 44(4): 187-200.
[2]	Gang LI,Zhijun WU. Task scheduling algorithm for system-wide information management based on multiple QoS constraints [J]. Journal on Communications, 2019, 40(7): 27-37.
[3]	Haoran LIU,Heyao ZHAO,Yujing DENG,Xingqi WANG,Rongrong YIN. Coverage control algorithm for wireless sensor networks based on non-cooperative game [J]. Journal on Communications, 2019, 40(1): 71-78.
[4]	Xiaoying ZHANG,Hui PENG,Hong CHEN. State-of-the-art survey of privacy-preserving data aggregation in wireless sensor networks [J]. Journal on Communications, 2018, 39(10): 130-142.
[5]	Guang-hai ZHOU,Zhao-long NING,Zhi-kui CHEN,Hua ZHONG,Yue-ming HU. Fault analysis and research of wireless sensor network based on kernel partial least squares [J]. Journal on Communications, 2017, 38(Z2): 94-98.
[6]	Miao YE,ping WANGYu,Cai DAI,li WANGXiao. New minimum exposure path problem and its solving algorithm in wireless sensor networks [J]. Journal on Communications, 2016, 37(1): 49-60.
[7]	. Research of malicious nodes identification based on DPAM-DM algorithm for WSN [J]. Journal on Communications, 2015, 36(Z1): 53-59.
[8]	Xiao-ding WANG,Li XU,Shu-ming ZHOU,Hui LIN. Fault diagnosis and restoration strategy based on Voronoi diagram and resolving set [J]. Journal on Communications, 2015, 36(Z1): 103-109.
[9]	Zhen CHEN,Jiang-hong HAN,Yong YANG,Zheng-yu LIU,Yang LU. Using idle TDMA slots for retransmitting packets cooperatively in VANET [J]. Journal on Communications, 2015, 36(7): 92-101.
[10]	Ru-yan WANG,Mei-ling ZHAI,Da-peng WU. Time series data aggregation algorithm with synchronous prediction for WBAN [J]. Journal on Communications, 2015, 36(6): 13-21.
[11]	Xiao-guang NIU,Chuan-bo WEI,Wei-jiang FENG,Guo-jun PENG,Huan-guo ZHANG. ONSA:optimal non-uniformly statistic-source anonymity protocol in WSN [J]. Journal on Communications, 2015, 36(6): 66-77.
[12]	Ming HE,Wen-hui LIANG,Qiu-li CHEN,Xi-liang CHEN,Jian CHEN. Optimization method through topology reconfiguration for mobile underwater wireless sensor networks [J]. Journal on Communications, 2015, 36(6): 78-87.
[13]	HOUWei Z,INGBo J,UANGYi-feng H,IAOXiao-xuan J,UJia-xing H,IANGWei L. CS-based data collection method for airborne clustering WSN [J]. Journal on Communications, 2015, 36(5): 130-139.
[14]	Xu LU,Liang-lun CHENG,Shi-liang LUO. Adaptive node scheduling algorithm for target tracking in wireless sensor networks [J]. Journal on Communications, 2015, 36(4): 70-80.
[15]	Hong-long CHEN,Zhi-bo WANG,Zhi WANG,Jiang-ming XU,Yan-jun LI,Li-ping LIU. Secure localization scheme against wormhole attack for wireless sensor networks [J]. Journal on Communications, 2015, 36(3): 33-40.