The week's pick
Reseach Article
Efficient Local Broadcast Algorithms in Wireless Ad Hoc Networks using Static and Dynamic Approaches
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 62 - Number 21 |
| Year of Publication: 2013 |
| Authors: R. Madhanmohan, K. Parkavi |
10.5120/10220-4939
|
R. Madhanmohan, K. Parkavi . Efficient Local Broadcast Algorithms in Wireless Ad Hoc Networks using Static and Dynamic Approaches. International Journal of Computer Applications. 62, 21 ( January 2013), 19-23. DOI=10.5120/10220-4939
Abstract
One of the fundamental operations in wireless ad hoc networks is broadcasting. To successfully reducing the number of transmissions of broadcast that are required to achieve full delivery with energy consumption using local broadcast algorithm. This broadcast algorithm is proposed for guarantee with full delivery and successful approximation to the optimum solution without considering the node position. There are two main approaches, static and dynamic, to broadcast algorithms in wireless ad hoc networks. Using the local topology information, the local algorithm determines the status of each node and also the priority function. In this paper the static approach in local broadcast algorithm is explained first. Using this approach it is not possible to achieve the good approximation factor to the optimum solution. If the position information is available, the constant approximation factor is got. But in dynamic approach the position of the node is determined "on-the-fly" based on local topology information. So, it is possible to get the good approximation factor to the optimum solution in dynamic approach of local broadcast algorithm. The position information is the solution for getting good approximation factor. But in some applications it may not be possible to get position information. Therefore, it is need to know whether local broadcast algorithms can achieve a constant approximation factor without using position information based on dynamic approach. To simplifying this problem, a local broadcast is designed in which the status of each node is decided "on-the-fly" (i. e. reactive protocol) and proves that the algorithm can achieve both full delivery and a constant approximation to the optimum solution.
References
- S. Ni, Y. Tseng, Y. Chen, and J. Sheu, "The Broadcast Storm Problem in a Mobile Ad Hoc Network," Proc. ACM MobiCom, pp. 151-162, 1999.
- I. Stojmenovic, M. Seddigh, and J. Zunic, "Dominating Sets and Neighbor Elimination-Based Broadcasting Algorithms in Wireless Networks," IEEE Trans. Parallel and Distributed Systems, vol. 13, no. 1, pp. 14-25, Jan. 2002.
- P. Wan, K. Alzoubi, and O. Frieder, "Distributed Construction of Connected Dominating Set in Wireless Ad Hoc Networks," Proc. IEEE INFOCOM, vol. 3, pp. 1597-1604, 2002.
- J. Wu and H. Li, "On Calculating Connected Dominating Set for Efficient Routing in Ad Hoc Wireless Networks," Proc. Int'l Workshop Discrete Algorithms and Methods for Mobile Computing and Comm. (DiaLM '99), pp. 7-14, 1999.
- M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. , 1990.
- B. Clark, C. Colbourn, and D. Johnson, "Unit Disk Graphs," Discrete Math. , vol. 86, pp. 165-177, 1990.
- J. Wu and F. Dai, "Broadcasting in Ad Hoc Networks Based on Self-Pruning," Proc. IEEE INFOCOM, pp. 2240-2250, 2003.
- W. Peng and X. Lu, "On the Reduction of Broadcast Redundancy in Mobile Ad Hoc Networks," Proc. ACM MobiHoc, pp. 129-130, 2000.
- J. Wu, W. Lou, and F. Dai, "Extended Multipoint Relays to Determine Connected Dominating Sets in Manets," IEEE Trans. Computers, vol. 55, no. 3, pp. 334-347, Mar. 2006.
- J. Wu and F. Dai, "A Generic Distributed Broadcast Scheme in Ad Hoc Wireless Networks," IEEE Trans. Computers, vol. 53, no. 10, pp. 1343-1354, Oct. 2004.
- H. Liu, P. Wan, X. Jia, X. Liu, and F. Yao, "Efficient Flooding Scheme Based on 1-Hop Information in Mobile Ad Hoc Networks," Proc. IEEE INFOCOM, 2006.
- M. Khabbazian and V. K. Bhargava, "Efficient Broadcasting in Mobile Ad Hoc Networks," IEEE Trans. Mobile Computing, vol. 8, no. 2, pp. 231-245, Feb. 2009.
- J. Wu and W. Lou, "Forward-Node-Set-Based Broadcast in Clustered Mobile Ad Hoc Networks," Wireless Comm. and Mobile Computing, vol. 3, no. 2, pp. 155-173, 2003.
- C. T. Zahn, "Black Box Maximization of Circular Coverage," J. Research of the Nat'l Bureau of Standards B. , vol. 66, pp. 181-216, 1962.
- M. Khabbazian and V. K. Bhargava, "Localized Broadcasting with Guaranteed Delivery and Bounded Transmission Redundancy," IEEE Trans. Computers, vol. 57, no. 8, pp. 1072-1086, Aug. 2008.
Index Terms
Keywords