Weitere Artikel dieser Ausgabe durch Wischen aufrufen
In this paper, the well-known network backbone formation problem is modeled as the stochastic min-degree constrained minimum spanning tree (md-MST) problem, where the link duration is associated with the edge weight. Then, a decentralized learning automata-based algorithm is proposed to form the most stable backbone of the wireless mobile ad hoc network (MANET) by finding a near optimal solution to the stochastic md-MST problem of the network topology graph. The proposed method significantly decreases the network overhead and shortens the network delay by reducing the number of intermediate forwarding hosts. It also extends the backbone lifetime by selection of the links with the maximum expected duration. The convergence of the proposed algorithm to the most stable network backbone is proven on the basis of the Martingale theorem. Several simulation experiments are conducted to investigate the efficiency of the proposed backbone formation algorithm. Numerical results show the superiority of the proposed method over the existing methods in terms of the backbone lifetime, end-to-end delay, backbone size, packet delivery ratio, and control message overhead.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
Basagni, S., Conti, M., & Stojmenovic, I. (2004). Mobile Ad hoc networking. New York: IEEE Press. CrossRef
Mohapatra, P., & Krishnamurthy, S. (2005). Ad hoc networks: technologies and protocols. Berlin: Springer Science. CrossRef
Lin, Z., Xu, L., Wang, D., & Gao, J. (2006). A coloring based backbone construction algorithm in wireless Ad Hoc network. Lecture Notes in Computer Science, 3947, 509–516. CrossRef
Almeida, A. M., Martins, P., & Souza, M. (2006). Min-degree constrained minimum spanning tree problem: Complexity, proprieties and formulations. Operations Research Center, University of Lisbon, working-paper, No. 6.
Li, Y., Thai, M. T., Wang, F., Yi, C. W., Wang, P. J., & Du, D. Z. (2005). On greedy construction of connected dominating sets in wireless networks. Wireless Communications and Mobile Computing (WCMC) (special issue).
Alzoubi, K. M., Li, X. Y., Wang, Y., Wan, P. J., & Frieder, O. (2003). Geometric spanners for wireless Ad Hoc network. IEEE Transactions on Parallel and Distributed Systems, 14(4), 408–421. CrossRef
Dai, F., & Wu, J. (2004). An extended localized algorithm for connected dominating set formation in Ad Hoc wireless networks. IEEE Transactions on Parallel and Distributed Systems (to appear)
Butenko, S., Cheng, X., Oliveira, C., & Pardalos, P. M. (2004). A new heuristic for the minimum connected dominating set problem on Ad Hoc wireless networks (pp. 61–73). Kluwer. In Recent Developments in Cooperative Control and Optimization.
Cheng, X., Ding, M., Hongwei, D., & Jia, X. (2006). Virtual backbone construction in multihop Ad Hoc wireless networks. Journal of Wireless Communications and Mobile Computing, 6, 183–190. CrossRef
Paul, B., Rao, S. V., & Nandi, S. (2005). An efficient distributed algorithm for finding virtual backbones in wireless Ad-Hoc networks. Lecture Notes in Computer Science, 3769, 302–311. CrossRef
Smys, S., & Josemin Bala, G. (2011). Efficient self-organized backbone formation in mobile ad hoc networks (MANETs). Computers and Electrical Engineering. doi: 10.1016/j.compeleceng.2011.03.006.
Hökelek, I., Uyar, M. Ü., & Fecko, M. A. (2008). On stability analysis of virtual backbone in mobile ad hoc networks. Wireless Networks, 14, 87–102. CrossRef
Dagdeviren, O., & Erciyes, K. (2006). A distributed backbone formation algorithm for mobile Ad Hoc networks. Lecture Notes in Computer Science, 4330, 219–230. CrossRef
Li, V., Park, H. S., & Oh, H. (2006). A cluster-label-based mechanism for backbones on mobile Ad Hoc networks. Lecture Notes in Computer Science, 3970, 26–36. CrossRef
Almeida, A. M., Martins, P., & Souza, M. C. (2010). md-MST is NP-hard for d \(\ge \)3. Electronic Notes in Discrete Mathematics, 36, 9–15. CrossRef
Martinez, L. C., & Cunha, A. S. (2010). Finding min-degree constrained spanning trees faster with a Branch-and-cut algorithm. Electronic Notes in Discrete Mathematics, 36, 311–318. CrossRef
Thathachar, M. A. L., & Harita, B. R. (1987). Learning automata with changing number of actions. IEEE Transactions on Systems, Man, and Cybernetics, SMG17, 1095–1100.
Narendra, K. S., & Thathachar, K. S. (1989). Learning automata: An introduction. New York: Printice-Hall.
Akbari Torkestani, J. (2012). An adaptive heuristic to the bounded diameter minimum spanning tree problem. Soft Computing, 16(11), 1977–1988.
Akbari Torkestani, J., & Meybodi, M. R. (2012). Finding minimum weight connected dominating set in stochastic graph based on learning automata. Information Sciences, 200, 57–77.
Akbari Torkestani, J. (2012). A learning automata-based solution to the bounded diameter minimum spanning tree problem. Journal of the Chinese Institute of Engineers (to appear).
Akbari Torkestani, J. (2012). Backbone formation in wireless sensor networks. Sensors and Actuators A: Physical, 185, 117–126.
Akbari Torkestani, J. (2012). LAAP: A learning automata-based adaptive polling scheme for clustered wireless Ad-hoc networks. Wireless Personal Communication (to appear).
Akbari Torkestani, J. (2012). Mobility prediction in mobile wireless networks. Journal of Network and Computer Applications, 35(5), 1633–1645.
Akbari Torkestani, J. (2012). A new distributed job scheduling algorithm for grid systems. Cybernetics and Systems (to appear).
Akbari Torkestani, J. (2012). A distributed resource discovery algorithm for P2P grids. Journal of Network and Computer Applications, 35(6), 2028–2036.
Akbari Torkestani, J. (2012). A new approach to the job scheduling problem in computational grids. Cluster Computing, 15(3), 201–210.
Akbari Torkestani, J. (2012). An adaptive learning to rank algorithm: Learning automata approach. Decision Support Systems, 54(1), 574–583.
Akbari Torkestani, J. (2012). An adaptive focused web crawling algorithm based on learning automata. Applied Intelligence, 37(4), 586–601.
Akbari Torkestani, J. (2012). An adaptive learning automata-based ranking function discovery algorithm. Journal of Intelligent Information Systems, 39(2), 441–459.
Ballardie, A., Francis, P., & Crowcroft, J. (1993). Core-based trees (CBT): An architecture for scalable inter-domain multicast routing. Computer Communication Review, 23(4), 85–95.
IEEE Computer Society LAN MAN Standards Committee, Wireless LAN Medium Access Protocol (MAC) and Physical Layer (PHY) specification, IEEE Standard 802.11-1997, The Institute of Electrical and Electronics Engineers, New York, 1997.
- Mobility-Based Backbone Formation in Wireless Mobile Ad-hoc Networks
Javad Akbari Torkestani
- Springer US