Conference Paper2006Cited by 1

Maintaining a binary tree structure for mobile ad hoc computing

Salahuddin Mohammad Masum, Amin Ahsan Ali

11th IEEE Symposium on Computers and Communications (ISCC'06)

IEEE, pp. 201–206

DOI: 10.1109/iscc.2006.95URL

Abstract

Mobile ad hoc (multi-hop) wireless network, unlike conventional infrastructured wireless counterparts, operates in the absence of fixed switching stations and thus all networking entities therein can be mobile. In mobile ad hoc network, logical binary tree structure is likely to become volatile or expensive to maintain over time due to changeable network topology. Additional adverse effects take place when a node joins or leaves the computation in the presence of mobility. This paper presents a distributed algorithm that maintains a binary tree among mobile nodes to the network dynamics to reflect overall communication efficiency. This is achieved by modifying the tree structure in a localized, mutual exclusive fashion, thereby allowing for concurrent segment-wise modifications to proceed. Remarkably our proposal operates without global knowledge of the logical structure and can be embodied as an underlying protocol layer that supports transparent deployments of conventional algorithms in mobile environment. Moreover, correctness proofs show that our proposal is promising.

Keywords

  • mobile ad hoc networks
  • distributed algorithms
  • node mobility
  • correctness proofs
  • network topology dynamics
  • communication efficiency

CCDS Authors

Amin Ahsan Ali, PhD
Amin Ahsan Ali, PhD

Amin Ahsan Ali, PhD

  • Director, AI/ML Wing

Professor

Department of Computer Science and Engineering

Independent University, Bangladesh

Published at

ACL, CHI, UbiComp, ECCV, IJCAI, ECAI, WACV, IPSN, PAKDD, LREC, IJCNN, ICPR, ICIP, BEA, BLP, ICMLA, Scientific Reports, Scientific Data, Pattern Recognition, Information Sciences, Ad Hoc Networks, Drug and Alcohol Dependence, PLOS ONE

Research Interests

Artificial Intelligence, Machine Learning

References

  1. 1.E.M. Royer, Chai-Keong Toh. (1999). A review of current routing protocols for ad hoc mobile wireless networks. IEEE Personal Communications, 6(2), 46–55[10.1109/98.760423]
  2. 2.Mario Gerla, Jack Tzu-Chieh Tsai. (1995). Multicluster, mobile, multimedia radio network. Wireless Networks, 1(3), 255–265[10.1007/bf01200845]
  3. 3.Hector Garcia-Molina, Daniel Barbara. (1985). How to assign votes in a distributed system. Journal of the ACM, 32(4), 841–860[10.1145/4221.4223]
  4. 4.Ernest Chang, Rosemary Roberts. (1979). An improved algorithm for decentralized extrema-finding in circular configurations of processes. Communications of the ACM, 22(5), 281–283[10.1145/359104.359108]
  5. 5.Divyakant Agrawal, Amr El Abbadi. (1991). An efficient and fault-tolerant solution for distributed mutual exclusion. ACM Transactions on Computer Systems, 9(1), 1–20[10.1145/103727.103728]
  6. 6.Gary L. Peterson. (1982). An <i>O</i> ( <i>n</i> log <i>n</i> ) Unidirectional Algorithm for the Circular Extrema Problem. ACM Transactions on Programming Languages and Systems, 4(4), 758–762[10.1145/69622.357194]
  7. 7.Elena Pagani, Gian Paolo Rossi. (1997). Reliable broadcast in mobile multihop packet networks. , 34–42[10.1145/262116.262125]
  8. 8.Ching-Chuan Chiang, M. Gerla. (2002). Routing and multicast in multihop, mobile wireless networks. Proceedings of ICUPC 97 - 6th International Conference on Universal Personal Communications, 2, 546–551[10.1109/icupc.1997.627224]
  9. 9.Avi Silberschatz, Peter Galvin, Greg Gagne. (1999). Applied Operating System Concepts.
  10. 10.B. R. Badrinath, Arup Acharya, Tomasz Imieliński. (1993). Impact of mobility on distributed computations. ACM SIGOPS Operating Systems Review, 27(2), 15–20[10.1145/155848.155853]
  11. 11.B.R. Badrinath, A. Acharya, T. Imielinski. (2002). Structuring distributed algorithms for mobile hosts. , 21–28[10.1109/icdcs.1994.302386]
  12. 12.(2000). Applied operating system concepts. Computers & Mathematics with Applications, 40(2-3), 420[10.1016/s0898-1221(00)90219-0]
  13. 13.Z. Tang, J.J. Garcia-Luna-Aceves. (2000). Hop reservation multiple access for multichannel packet radio networks. Computer Communications, 23(10), 877–886[10.1016/s0140-3664(99)00214-5]
  14. 14.Jehn-Ruey Jiang, Shing-Tsaan Huang, Yu-Chen Kuo. (1997). Cohorts structures for fault-tolerant k entries to a critical section. IEEE Transactions on Computers, 46(2), 222–228[10.1109/12.565603]
  15. 15.Li-Hsing Yen, Kuang-Hwei Chi. (2004). Maintaining a ring structure for mobile ad hoc computing. Journal of Parallel and Distributed Computing, 64(12), 1371–1379[10.1016/j.jpdc.2004.08.005]
  16. 16.I. Nikolaidis, J.J. Harms. (2005). A logical ring reliable multicast protocol for mobile nodes. , 106–113[10.1109/icnp.1999.801921]
  17. 17.L.M. Patnaik, A.K. Ramakrishna, R. Muralidharan. (1997). Distributed algorithms for mobile hosts. IEE Proceedings - Computers and Digital Techniques, 144(2), 49[10.1049/ip-cdt:19970952]
  18. 18.W. Jia. (1999). A Multicast Protocol Based on a Single Logical Ring Using a Virtual Token and Logical Clocks. The Computer Journal, 42(3), 202–220[10.1093/comjnl/42.3.202]
  19. 19.Weijia Jia, Jiannong Cao, To-Yat Cheung. (2002). A multicast protocol based on a single logical ring using a virtual token and logical clocks. , 1, 85–92[10.1109/icpp.1996.537147]

Cited By

  1. 1.D. Shukla, Yashwant Singh Rajput, Narendra Singh Thakur. (2013). Edge Estimation in the Population of a Binary Tree Using Node-Sampling. Communication in Statistics- Theory and Methods, 43(13), 2815–2829[10.1080/03610926.2012.685552]
← All publications