Please wait a minute...
Frontiers of Computer Science

ISSN 2095-2228

ISSN 2095-2236(Online)

CN 10-1014/TP

邮发代号 80-970

2019 Impact Factor: 1.275

Frontiers of Computer Science  2023, Vol. 17 Issue (4): 174502   https://doi.org/10.1007/s11704-022-1288-1
  本期目录
Robust load-balanced backbone-based multicast routing in mobile opportunistic networks
Di ZHANG(), Dong ZHAO, Huadong MA
Beijing Key Laboratory of Intelligent Telecommunications Software and Multimedia, Beijing University of Posts and Telecommunications, Beijing 100876, China
 全文: PDF(9980 KB)   HTML
Abstract

Mobile opportunistic network (MON) is an efficient way of communication when there is no persistent connection between nodes. Multicast in MONs can be used to efficiently deliver messages to multiple destination nodes. However, because multiple destination nodes are involved, multicast routing is more complex than unicast and brings a higher communication cost. Backbone-based routing can effectively reduce the network overhead and the complexity of routing scheme. However, the load of backbone nodes is larger than that of regular nodes. If the backbone node’s buffer is exhausted, it will have a significant impact on the performance of the routing scheme. Load balancing can improve the ability of backbone to deal with the change of network load, and backbone maintenance algorithm can provide backbone robustness. In this paper, we propose a robust load-balanced backbone-based multicast routing scheme in MONs. In the backbone construction algorithm, we transform the problem of backbone construction into a multi-objective optimization problem, and propose a multi-objective evolutionary algorithm-based backbone construction algorithm, namely LBMBC-MOEA algorithm. In addition, in order to increase the robustness of the backbone-based routing scheme, we propose a localized multicast backbone maintenance algorithm (MBMA) to deal with the buffer exhaustion of backbone nodes. When a backbone node’s residual buffer is insufficient, MBMA algorithm selects other nodes to replace the backbone node. The results on extensive simulations show that when considering the node buffer size constraints, compared with previous backbone-based multicast routing schemes, our proposed algorithm has better performance, and when the node’s residual buffer is insufficient, MBMA algorithm can significantly improve the performance of the backbone-based multicast routing scheme.

Key wordsmobile opportunistic network    multicast    multi-objective optimization    backbone construction    backbone maintenance
收稿日期: 2021-10-02      出版日期: 2022-11-07
Corresponding Author(s): Di ZHANG   
 引用本文:   
. [J]. Frontiers of Computer Science, 2023, 17(4): 174502.
Di ZHANG, Dong ZHAO, Huadong MA. Robust load-balanced backbone-based multicast routing in mobile opportunistic networks. Front. Comput. Sci., 2023, 17(4): 174502.
 链接本文:  
https://academic.hep.com.cn/fcs/CN/10.1007/s11704-022-1288-1
https://academic.hep.com.cn/fcs/CN/Y2023/V17/I4/174502
Fig.1  
Fig.2  
Fig.3  
Fig.4  
Fig.5  
Fig.6  
  
  
  
Parameter Value
Message size [500 KB,1 MB]
Transmit speed 250k Bps
Population size 20
Generation size maxGen 100
Crossover probability PCross 0.9
Mutation probability Pmuta 0.1
Tab.1  
Parameter Value
Duration 100000 s
Simulation region 1000 × 1000 m2
Node speed (m/s) [0.5,1]
Wait time/s [0, 60]
Transmit range 10 m
Tab.2  
Fig.7  
Fig.8  
Fig.9  
Fig.10  
Fig.11  
Fig.12  
Fig.13  
Fig.14  
  
  
  
1 L, Pelusi A, Passarella M Conti . Opportunistic networking: data forwarding in disconnected mobile ad hoc networks. IEEE communications Magazine, 2006, 44( 11): 134–141
2 R K, Ganti F, Ye H Lei . Mobile crowdsensing: current state and future challenges. IEEE Communications Magazine, 2011, 49( 11): 32–39
3 H D, Ma D, Zhao P Y Yuan . Opportunities in mobile crowd sensing. IEEE Communications Magazine, 2014, 52( 8): 29–35
4 H, Hartenstein L P Laberteaux . A tutorial survey on vehicular ad hoc networks. IEEE Communications Magazine, 2008, 46( 6): 164–171
5 Y, Wang Y, Liu J, Zhang H, Ye Z Tan . Cooperative store-carry-forward scheme for intermittently connected vehicular networks. IEEE Transactions on Vehicular Technology, 2017, 66( 1): 777–784
6 U, Lee S Y, Oh K W, Lee M Gerla . RelayCast: scalable multicast routing in delay tolerant networks. In: Proceedings of 2008 IEEE International Conference on Network Protocols. 2008, 218–227
7 Y, Wang X, Li J Wu . Multicasting in delay tolerant networks: delegation forwarding. In: Proceedings of 2010 IEEE Global Telecommunications Conference GLOBECOM 2010. 2010, 1–5
8 W, Gao Q, Li B, Zhao G Cao . Social-aware multicast in disruption-tolerant networks. IEEE/ACM Transactions on Networking, 2012, 20( 5): 1553–1566
9 X, Chen C, Shang B, Wong W, Li S Oh . Efficient multicast algorithms in opportunistic mobile social networks using community and social features. Computer Networks, 2016, 111: 71–81
10 Q, Ye L, Cheng M C, Chuah B D Davison . OS-multicast: on-demand situation-aware multicasting in disruption tolerant networks. In: Proceedings of the 63rd IEEE Vehicular Technology Conference. 2006, 96–100
11 T, Liu Y, Zhu R, Jiang B Li . A sociality-aware approach to computing backbone in mobile opportunistic networks. Ad Hoc Networks, 2015, 24: 46–56
12 S, Yang J Wu . Adaptive backbone-based routing in delay tolerant networks. In: Proceedings of the 10th IEEE International Conference on Mobile Ad-Hoc and Sensor Systems. 2013, 356–364
13 W, Zhao M, Ammar E Zegura . Multicasting in delay tolerant networks: semantic models and routing algorithms. In: Proceedings of 2005 ACM SIGCOMM Workshop on Delay-Tolerant Networking. 2005, 268–275
14 Q, Ye C, Liang M C, Chuah B D Davison . Performance comparison of different multicast routing strategies in disruption tolerant networks. Computer Communications, 2009, 32( 16): 1731–1741
15 Y, Liu A M A E, Bashar F, Li Y, Wang K Liu . Multi-copy data dissemination with probabilistic delay constraint in mobile opportunistic device-to-device networks. In: Proceedings of the 17th IEEE International Symposium on A World of Wireless, Mobile and Multimedia Networks. 2016, 1–9
16 Y, Liu H, Wu Y, Xia Y, Wang F, Li P Yang . Optimal online data dissemination for resource constrained mobile opportunistic networks. IEEE Transactions on Vehicular Technology, 2017, 66( 6): 5301–5315
17 L, Galluccio B, Lorenzo S Glisic . Sociality-aided new adaptive infection recovery schemes for multicast DTNs. IEEE Transactions on Vehicular Technology, 2016, 65( 5): 3360–3376
18 A, Roy S, Bose T, Acharya S DasBit . Social-based energy-aware multicasting in delay tolerant networks. Journal of Network and Computer Applications, 2017, 87: 169–184
19 K, Xu X, Hong M Gerla . Landmark routing in ad hoc networks with mobile backbones. Journal of Parallel and Distributed Computing, 2003, 63( 2): 110–122
20 A, Srinivas E Modiano . Joint node placement and assignment for throughput optimization in mobile backbone networks. IEEE Journal on Selected Areas in Communications, 2012, 30( 5): 975–985
21 S, Chu P, Wei X, Zhong X, Wang Y Zhou . Deployment of a connected reinforced backbone network with a limited number of backbone nodes. IEEE Transactions on Mobile Computing, 2013, 12( 6): 1188–1200
22 W R, Heinzelman A, Chandrakasan H Balakrishnan . Energy-efficient communication protocol for wireless microsensor networks. In: Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. 2000, 10–20
23 O, Younis S Fahmy . HEED: a hybrid, energy-efficient, distributed clustering approach for ad hoc sensor networks. IEEE Transactions on Mobile Computing, 2004, 3( 4): 366–379
24 J, Yu N, Wang G, Wang D Yu . Connected dominating sets in wireless ad hoc and sensor networks — a comprehensive survey. Computer Communications, 2013, 36( 2): 121–134
25 T, Liu Y, Zhu R, Jiang B Li . A sociality-aware approach to computing backbone in mobile opportunistic networks. In: Proceedings of 2013 IEEE Global Communications Conference. 2013, 389–394
26 D, Zhang H, Ma D Zhao . Social-aware backbone-based multicast routing in mobile opportunistic networks. In: Proceedings of the 3rd International Conference on Big Data Computing and Communications. 2017, 31–38
27 J, He S, Ji P, Fan Y, Pan Y Li . Constructing a load-balanced virtual backbone in wireless sensor networks. In: Proceedings of 2012 International Conference on Computing, Networking and Communications. 2012, 959–963
28 Z, Ruble M Stefanovic . Load balanced connected dominating set for mobile ad hoc networks. In: Proceedings of the 6th International Symposium on Communications, Control and Signal Processing. 2014, 606–610
29 G, Kumar M K Rai . An energy efficient and optimized load balanced localization method using CDS with one-hop neighbourhood and genetic algorithm in WSNs. Journal of Network and Computer Applications, 2017, 78: 73–82
30 B, Liang Z J Haas . Virtual backbone generation and maintenance in ad hoc network mobility management. In: Proceedings of IEEE INFOCOM 2000 Conference on Computer Communications. Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. 2000, 1293–1302
31 K, Sakai M T, Sun W S, Ku H Okada . Maintaining CDS in mobile ad hoc networks. In: Proceedings of the 3rd International Conference on Wireless Algorithms, Systems, and Applications. 2008, 141–153
32 A, Srinivas G, Zussman E Modiano . Construction and maintenance of wireless mobile backbone networks. IEEE/ACM Transactions on Networking, 2009, 17( 1): 239–252
33 K, Xing S, Zhang L, Shi H, Zhu Y Wang . A localized backbone renovating algorithm for wireless ad hoc and sensor networks. In: Proceedings of 2013 IEEE INFOCOM. 2013, 2184–2192
34 J, Wang E, Kodama T Takata . Construction and maintenance of K-hop CDS in mobile ad hoc networks. In: Proceedings of the 31st IEEE International Conference on Advanced Information Networking and Applications. 2017, 220–227
35 J, Scott R, Gass J, Crowcroft P, Hui C, Diot A Chaintreau . The cambridge/haggle dataset (v. 2009-05-29). See Crawdad.org/cambridge/haggle/ website, 2018
36 N, Eagle A Pentland . The mit/reality dataset (v. 2005-07-01). See Crawdad.org/mit/reality/ website, 2018
37 E M, Daly M Haahr . Social network analysis for routing in disconnected delay-tolerant MANETs. In: Proceedings of the 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing. 2007, 32–40
38 P, Hui J, Crowcroft E Yoneki . BUBBLE rap: social-based forwarding in delay-tolerant networks. IEEE Transactions on Mobile Computing, 2011, 10( 11): 1576–1589
39 K, Deb A, Pratap S, Agarwal T Meyarivan . A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6( 2): 182–197
40 A, Lindgren A, Doria O Schelén . Probabilistic routing in intermittently connected networks. In: Proceedings of the 1st International Workshop on Service Assurance with Partial and Intermittent Resources. 2004, 239–254
41 B Y, Wu K M Chao . Spanning Trees and Optimization Problems. London: Chapman & Hall Led, 2004
42 S, Guha S Khuller . Approximation algorithms for connected dominating sets. Algorithmica, 1998, 20( 4): 374–387
43 B, Bringmann M, Berlingerio F, Bonchi A Gionis . Learning and predicting the evolution of social networks. IEEE Intelligent Systems, 2010, 25( 4): 26–35
44 A, Keränen J, Ott T Kärkkäinen . The ONE simulator for DTN protocol evaluation. In: Proceedings of the 2nd International Conference on Simulation Tools and Techniques. 2009, 55
45 D B, Johnson D A Maltz . Dynamic source routing in ad hoc wireless networks. In: Imielinski T, Korth H F, eds. Mobile Computing. Boston: Springer, 1994, 153–181
46 M, Abdulla R Simon . Characteristics of common mobility models for opportunistic networks. In: Proceedings of the 2nd ACM Workshop on Performance Monitoring and Measurement of Heterogeneous Wireless and Wired Networks. 2007, 105–109
[1] FCS-21288-OF-DZ_suppl_1 Download
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed