IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v10y2022i18p3321-d913944.html
   My bibliography  Save this article

A D2D Group Communication Scheme Using Bidirectional and InCremental A-Star Search to Configure Paths

Author

Listed:
  • Wei Kuang Lai

    (Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, Taiwan)

  • Chin-Shiuh Shieh

    (Department of Electronic Engineering, National Kaohsiung University of Science and Technology, Kaohsiung 807618, Taiwan)

  • Chao-Ping Yang

    (Department of Computer Science and Engineering, National Sun Yat-sen University, Kaohsiung 80424, Taiwan)

Abstract

The Device-to-Device (D2D) communication introduced in 3GPP’s Release 12 is a promising option for the accommodation of increasing traffic demand and the alleviation of core networks’ loading. The D2D communication mode prevails in scenarios where mobile users in proximity form a communication group sharing the same interest in digital content. A user can download intended content from peers in the same communication group rather than from the Internet via the base station. This article addresses the routing issue within D2D communication groups. It is, in effect, a path selection problem. We define a utility function considering both delay and throughput. The path selection problem can be formulated as an NP-hard optimization problem. A Bidirectional and InCremental A-star (BICA*) algorithm incorporating the concept of bidirectional search and lifelong planning is developed to tackle the NP-hard optimization problem. Simulations reveal that the proposed approach outperforms existing ones in terms of less delay, higher throughput, and higher satisfaction ratio. The Greedy approach, Two-Stage Relay Selection (TSRS), and the standard A* algorithm were included in the comparative study. The throughput improvements of the proposed scheme are up to 23% and 46.5% compared to TSRS and Greedy, respectively. The proposed scheme possesses the lowest delay and the highest satisfaction rate, among others. With less computational time, the proposed BICA* is more responsive than the standard A* in dynamic environments.

Suggested Citation

  • Wei Kuang Lai & Chin-Shiuh Shieh & Chao-Ping Yang, 2022. "A D2D Group Communication Scheme Using Bidirectional and InCremental A-Star Search to Configure Paths," Mathematics, MDPI, vol. 10(18), pages 1-28, September.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:18:p:3321-:d:913944
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/18/3321/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/18/3321/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. G. B. Dantzig & J. H. Ramser, 1959. "The Truck Dispatching Problem," Management Science, INFORMS, vol. 6(1), pages 80-91, October.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Jumbo, Olga & Moghaddass, Ramin, 2022. "Resource optimization and image processing for vegetation management programs in power distribution networks," Applied Energy, Elsevier, vol. 319(C).
    2. Babagolzadeh, Mahla & Zhang, Yahua & Abbasi, Babak & Shrestha, Anup & Zhang, Anming, 2022. "Promoting Australian regional airports with subsidy schemes: Optimised downstream logistics using vehicle routing problem," Transport Policy, Elsevier, vol. 128(C), pages 38-51.
    3. Tianlu Zhao & Yongjian Yang & En Wang, 2020. "Minimizing the average arriving distance in carpooling," International Journal of Distributed Sensor Networks, , vol. 16(1), pages 15501477198, January.
    4. A. Mor & M. G. Speranza, 2020. "Vehicle routing problems over time: a survey," 4OR, Springer, vol. 18(2), pages 129-149, June.
    5. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    6. Pradhananga, Rojee & Taniguchi, Eiichi & Yamada, Tadashi & Qureshi, Ali Gul, 2014. "Bi-objective decision support system for routing and scheduling of hazardous materials," Socio-Economic Planning Sciences, Elsevier, vol. 48(2), pages 135-148.
    7. Yimei Chang & Jiaqi Yu & Yang Wang & Xiaoling Xie, 2025. "An Improved Salp Swarm Algorithm for Solving a Multi-Temperature Joint Distribution Route Optimization Problem," Mathematics, MDPI, vol. 13(4), pages 1-24, February.
    8. Qi, Mingyao & Lin, Wei-Hua & Li, Nan & Miao, Lixin, 2012. "A spatiotemporal partitioning approach for large-scale vehicle routing problems with time windows," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 48(1), pages 248-257.
    9. Srinivas, Sharan & Ramachandiran, Surya & Rajendran, Suchithra, 2022. "Autonomous robot-driven deliveries: A review of recent developments and future directions," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 165(C).
    10. Tibor Holczinger & Olivér Ősz & Máté Hegyháti, 2020. "Scheduling approach for on-site jobs of service providers," Flexible Services and Manufacturing Journal, Springer, vol. 32(4), pages 913-948, December.
    11. Zhiping Zuo & Yanhui Li & Jing Fu & Jianlin Wu, 2019. "Human Resource Scheduling Model and Algorithm with Time Windows and Multi-Skill Constraints," Mathematics, MDPI, vol. 7(7), pages 1-18, July.
    12. Narjes MASHHADI BANDANI & Alireza NADERI & Mohsen AKBARPOUR SHIRZAEI, 2017. "Cement Transportation Limited-Fleet Modeling And Assigning To Rated Demands," Transport Problems, Silesian University of Technology, Faculty of Transport, vol. 12(1), pages 111-123, March.
    13. Ji, Chenlu & Mandania, Rupal & Liu, Jiyin & Liret, Anne, 2022. "Scheduling on-site service deliveries to minimise the risk of missing appointment times," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    14. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    15. Yeo, Lip Siang & Teng, Sin Yong & Ng, Wendy Pei Qin & Lim, Chun Hsion & Leong, Wei Dong & Lam, Hon Loong & Wong, Yat Choy & Sunarso, Jaka & How, Bing Shen, 2022. "Sequential optimization of process and supply chains considering re-refineries for oil and gas circularity," Applied Energy, Elsevier, vol. 322(C).
    16. Müller, Juliane, 2010. "Approximative solutions to the bicriterion Vehicle Routing Problem with Time Windows," European Journal of Operational Research, Elsevier, vol. 202(1), pages 223-231, April.
    17. Martinhon, Carlos & Lucena, Abilio & Maculan, Nelson, 2004. "Stronger K-tree relaxations for the vehicle routing problem," European Journal of Operational Research, Elsevier, vol. 158(1), pages 56-71, October.
    18. Ling Gai & Ying Jin & Binyuan Zhang, 2022. "An integrated method for hybrid distribution with estimation of demand matching degree," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2782-2808, November.
    19. Jin Li & Feng Wang & Yu He, 2020. "Electric Vehicle Routing Problem with Battery Swapping Considering Energy Consumption and Carbon Emissions," Sustainability, MDPI, vol. 12(24), pages 1-20, December.
    20. Hatzenbühler, Jonas & Jenelius, Erik & Gidófalvi, Gyözö & Cats, Oded, 2023. "Modular vehicle routing for combined passenger and freight transport," Transportation Research Part A: Policy and Practice, Elsevier, vol. 173(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:10:y:2022:i:18:p:3321-:d:913944. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.