Structure-Free Broadcast Scheduling for Duty-Cycled Multihop Wireless Sensor Networks
ABSTARCT :
Broadcasting is an essential operation for the source node to disseminate the message to all other nodes in the network. Unfortunately, the problem of Minimum Latency Broadcast Scheduling (MLBS) in duty-cycled wireless networks is not well studied. In existing works, the construction of broadcast tree and the scheduling of transmissions are conducted separately, which may result in a bad-structured broadcast tree and then a large latency is obtained even using the optimal scheduling method. Thus, the MLBS problem in duty-cycled wireless networks without above limitation is investigated in this paper. Firstly, a two step scheduling algorithm is proposed to construct the broadcast tree and compute a collision-free schedule simultaneously. This is the first work that can integrate these two kinds of operations together. Secondly, a novel transmission mode, i.e., concurrent broadcasting, is first introduced for wireless networks and several techniques are designed to further improve the broadcast latency. Thirdly, through designing some special data structures, the continuous and all-to-all broadcasting algorithms are also proposed, in which all the nodes do not need to wait for any period of time to begin a new transmission. Finally, the theoretical analysis and experimental results demonstrate the efficiency of the proposed algorithms.
EXISTING SYSTEM :
? We present a formal equation for the MLAS problem in duty-cycled WSNs and analyze the drawbacks of existing schemes solving this problem.
? We present arguments to prove that DEDAS-D is a better approach to solve the MLAS problem in duty-cycled WSNs compared with other existing schemes.
? Many existing approaches solving the MLAS problem construct the data aggregation tree based on finding MIS or CDS.
? However, these data aggregation trees also have a high-degree bottleneck problem, i.e., many high degree nodes exist in the tree and thus reduce the number of concurrent transmissions.
DISADVANTAGE :
? In this paper, we investigate the MLBS problem in dutycycled multi-hop wireless networks (MLBSDC problem).
? We propose a novel approximation algorithm called OTAB for the one-to-all MLBSDC problem, and two approximation algorithms called UTB and UNB for the all-to-all MLBSDC problem under the unit-size and the unbounded-size message models respectively.
? The MLBS problem in multi-hop wireless networks has been proved to be NP-hard in, and several approximation algorithms, which follow the assumption that all the nodes are always active, have been proposed for this problem.
? We first present one novel approximation algorithm OTAB for the one-to-all MLBSDC problem.
PROPOSED SYSTEM :
• To the best of our knowledge, our paper is the first work that proposes a distributed approach to solve the MLAS problem in dutycycled WSNs.
• We prove the correctness of our proposed scheme and show that DEDAS-D is a better solution for this problem compared with previous schemes.
• Moreover, it is worth noting that the delay performance of DEDAS-D approximates to that of our previously proposed centralized approach.
• In this paper, we investigate the MLAS problem in duty-cycled WSNs and propose a novel distributed scheme to significantly reduce the data aggregation delay.
ADVANTAGE :
? We evaluate the performance of our algorithms by conducting extensive simulations under different network configurations.
? The performance of the OTAB and OTAB-P algorithms is compared with that of the ELAC algorithm.
? We study the effect of different network configurations including the network size, the transmission radius, and the duty cycle on the performance of the algorithms.
? We evaluate the impact of network size on the performance of the algorithms.
? In this paper, we further investigate the one-to-all and all-to-all MLBSDC problems and give efficient solutions for these problems.
|