Skip to main content
main-content
Top

Hint

Swipe to navigate through the chapters of this book

2020 | OriginalPaper | Chapter

Propagating Minimal Messages Using Multi Set-Cover in Wireless Ad-Hoc Network

share
SHARE

Abstract

Wireless (ad hoc) network is a group of nodes to communicate with each other over a wireless channel to receive and transmit data packets among their neighbors residing in the transmission range. We propose to build a wireless ad hoc network to maintain data transmission in a cost-effective way with minimal data packets. This transmission of data can commence in conditions/circumstances which are challenged and harsh to continue without failure caused by any network, environmental or other factors and ensure fault tolerance in such kind of noisy network. In spite of having vast research experiments in this area, existent studies shows lack effort in establishing both balanced coverage of two hop neighbors of sender and fault tolerance in the network with minimal message propagation at the same time. In this paper, a new algorithm using two hop distant neighbor information is proposed and a special version of set cover problem suited to ad hoc networks is used to output multiple forwarder lists by which, all the uncovered two hop neighbors are covered once. Extensive simulations made in NS2 implementation show that the algorithm provides high delivery rate (88% in average) of packets and transmission of average number of packets is lower than existent Dominant Pruning algorithm. Later we analyzed the reachability aspect of the algorithm by calculating the percentage of nodes (receivers) reached in presence of various fractions of malfunctioning nodes integrated deliberately by us in the network.
Literature
1.
go back to reference Rahman, A., Gburzynski, P., Kaminska, B.: Enhanced dominant pruning-based broadcasting in untrusted ad-hoc wireless networks. In: ICC, pp. 3389–3394 (2007) Rahman, A., Gburzynski, P., Kaminska, B.: Enhanced dominant pruning-based broadcasting in untrusted ad-hoc wireless networks. In: ICC, pp. 3389–3394 (2007)
2.
go back to reference Akter, M., Islam, A., Rahman, A.: Fault tolerant optimized broadcast for wireless ad-Hoc networks. In: 2016 International Conference Networking Systems and Security (NSysS) (2016) Akter, M., Islam, A., Rahman, A.: Fault tolerant optimized broadcast for wireless ad-Hoc networks. In: 2016 International Conference Networking Systems and Security (NSysS) (2016)
3.
go back to reference Lim, H., Kim, C.: Multicast tree construction and flooding in wireless ad hoc networks. In: Proceedings of the 3rd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, pp. 61–68. ACM (2000) Lim, H., Kim, C.: Multicast tree construction and flooding in wireless ad hoc networks. In: Proceedings of the 3rd ACM International Workshop on Modeling, Analysis and Simulation of Wireless and Mobile Systems, pp. 61–68. ACM (2000)
4.
go back to reference Peng, W., Lu, X.-C.: On the reduction of broadcast redundancy in mobile ad hoc networks. In: Proceedings of the 1st ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 129–130. IEEE Press (2000) Peng, W., Lu, X.-C.: On the reduction of broadcast redundancy in mobile ad hoc networks. In: Proceedings of the 1st ACM International Symposium on Mobile Ad Hoc Networking and Computing, pp. 129–130. IEEE Press (2000)
6.
go back to reference Even, S.: Graph Algorithms. Computer Science Press, Rockville (1979) MATH Even, S.: Graph Algorithms. Computer Science Press, Rockville (1979) MATH
7.
go back to reference Qayyum, A., Viennot, L., Laouiti, A.: Multipoint relaying: an efficient technique for flooding in mobile wireless networks. In: Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS 2002) (2002) Qayyum, A., Viennot, L., Laouiti, A.: Multipoint relaying: an efficient technique for flooding in mobile wireless networks. In: Proceedings of the 35th Annual Hawaii International Conference on System Sciences (HICSS 2002) (2002)
8.
go back to reference Sinha, P., Sivakumar, R., Vaduvur, B.: Enhancing ad hoc routing with dynamic virtual infrastructures. In: Proceedings of the IEEE INFOCOM 2001, pp. 1763–1772 (2001) Sinha, P., Sivakumar, R., Vaduvur, B.: Enhancing ad hoc routing with dynamic virtual infrastructures. In: Proceedings of the IEEE INFOCOM 2001, pp. 1763–1772 (2001)
9.
go back to reference Alzoubi, K.M., Wan, P.J., Frieder, O.: New distributed algorithm for connected dominating set in wireless ad hoc networks. In: Proceedings HICSS-35 (2002) Alzoubi, K.M., Wan, P.J., Frieder, O.: New distributed algorithm for connected dominating set in wireless ad hoc networks. In: Proceedings HICSS-35 (2002)
10.
go back to reference Calinescu, G., Mandoiu, I., Wan, P.J., Zelikovsky, A.: Selecting forwarding neighbors in wireless ad hoc networks. In: Proceedings of the ACM DIALM 2001, pp. 34–43, December 2001 Calinescu, G., Mandoiu, I., Wan, P.J., Zelikovsky, A.: Selecting forwarding neighbors in wireless ad hoc networks. In: Proceedings of the ACM DIALM 2001, pp. 34–43, December 2001
11.
go back to reference Tipper, D., Dahlberg, T., Shin, H., Charnsripinyo, C.: Providing fault tolerance in wireless access networks. IEEE Commun. Mag. 40(1), 58–64 (2002) CrossRef Tipper, D., Dahlberg, T., Shin, H., Charnsripinyo, C.: Providing fault tolerance in wireless access networks. IEEE Commun. Mag. 40(1), 58–64 (2002) CrossRef
12.
go back to reference Koushanfar, F., Potkonjak, M., Sangiovanni-Vincentell, A.: Fault tolerance techniques for wireless ad hoc sensor networks. In: 2002 Proceedings of IEEE Sensors, vol. 2. IEEE (2002) Koushanfar, F., Potkonjak, M., Sangiovanni-Vincentell, A.: Fault tolerance techniques for wireless ad hoc sensor networks. In: 2002 Proceedings of IEEE Sensors, vol. 2. IEEE (2002)
13.
go back to reference Kuhn, F., Moscibroda, T., Wattenhofer, R.: Fault-tolerant clustering in ad hoc and sensor networks. In: 2006 26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006. IEEE (2006) Kuhn, F., Moscibroda, T., Wattenhofer, R.: Fault-tolerant clustering in ad hoc and sensor networks. In: 2006 26th IEEE International Conference on Distributed Computing Systems, ICDCS 2006. IEEE (2006)
14.
go back to reference Soro, S., Heinzelman, W.B.: Cluster head election techniques for coverage preservation in wireless sensor networks. Ad Hoc Netw. 7(5), 955–972 (2009) CrossRef Soro, S., Heinzelman, W.B.: Cluster head election techniques for coverage preservation in wireless sensor networks. Ad Hoc Netw. 7(5), 955–972 (2009) CrossRef
15.
go back to reference Liang, J., Liu, M., Kui, X.: A survey of coverage problems in wireless sensor networks. Sens. Transd. 163(1), 240 (2014) Liang, J., Liu, M., Kui, X.: A survey of coverage problems in wireless sensor networks. Sens. Transd. 163(1), 240 (2014)
16.
go back to reference Chen, J., Kher, S., Somani, A.: Distributed fault detection of wireless sensor networks. In: Proceedings of the 2006 Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks, pp. 65–72. ACM (2006) Chen, J., Kher, S., Somani, A.: Distributed fault detection of wireless sensor networks. In: Proceedings of the 2006 Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks, pp. 65–72. ACM (2006)
17.
go back to reference Gupta, G., Younis, M.: Fault-tolerant clustering of wireless sensor networks. In: 2003 IEEE Wireless Communications and Networking, WCNC 2003, vol. 3, pp. 1579–1584. IEEE (2003) Gupta, G., Younis, M.: Fault-tolerant clustering of wireless sensor networks. In: 2003 IEEE Wireless Communications and Networking, WCNC 2003, vol. 3, pp. 1579–1584. IEEE (2003)
18.
go back to reference Paradis, L., Han, Q.: A survey of fault management in wireless sensor networks. J. Netw. Syst. Manag. 15(2), 171–190 (2007) CrossRef Paradis, L., Han, Q.: A survey of fault management in wireless sensor networks. J. Netw. Syst. Manag. 15(2), 171–190 (2007) CrossRef
19.
go back to reference Deng, J., Han, Y.S., Chen, P., Varshney, P.K.: Optimal transmission range for wireless ad hoc networks based on energy efficiency. IEEE Trans. Commun. 55(7), 1439–1439 (2007) CrossRef Deng, J., Han, Y.S., Chen, P., Varshney, P.K.: Optimal transmission range for wireless ad hoc networks based on energy efficiency. IEEE Trans. Commun. 55(7), 1439–1439 (2007) CrossRef
20.
go back to reference Tseng, Y.-C., Ni, S.-Y., Chen, Y.-S., Sheu, J.-P.: The broadcast storm problem in a mobile ad hoc network. Wirel. Netw. 8(2/3), 153–167 (2002) CrossRef Tseng, Y.-C., Ni, S.-Y., Chen, Y.-S., Sheu, J.-P.: The broadcast storm problem in a mobile ad hoc network. Wirel. Netw. 8(2/3), 153–167 (2002) CrossRef
21.
go back to reference Royer, E.M., Perkins, C.E.: An implementation study of the AODV routing protocol. In: 2000 IEEE Wireless Communications and Networking Conference, WCNC 2000, vol. 3, pp. 1003–1008. IEEE (2000) Royer, E.M., Perkins, C.E.: An implementation study of the AODV routing protocol. In: 2000 IEEE Wireless Communications and Networking Conference, WCNC 2000, vol. 3, pp. 1003–1008. IEEE (2000)
Metadata
Title
Propagating Minimal Messages Using Multi Set-Cover in Wireless Ad-Hoc Network
Author
Sadia Sharmin
Copyright Year
2020
DOI
https://doi.org/10.1007/978-3-030-39875-0_4