2015/04/21 by Mohammad R. Ataei, Amir H. Banihashemi, Ataei, Mohammad R. +3
Computer Science · #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI) #Opportunistic and Delay-Tolerant Networks
paper · pdf · doi:10.48550/arxiv.1504.05268
openalex publication_date 2015/04/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we propose solutions for the energy-efficient broadcasting over cross networks, where N nodes are located on two perpendicular lines. Our solutions consist of an algorithm which finds the optimal range assignment in polynomial time (O(N12)), a near-optimal algorithm with linear complexity (O(N)), and a distributed algorithm with complexity O(1). To the best of our knowledge, this is the first study presenting an optimal solution for the minimum-energy broadcasting problem for a 2-D network (with cross configuration). We compare our algorithms with the broadcast incremental power (BIP) algorithm, one of the most commonly used methods for solving this problem with complexity O(N2). We demonstrate that our near-optimal algorithm outperforms BIP, and that the distributed algorithm performs close to it. Moreover, the proposed distributed algorithm can be used for more general two-dimensional networks, where the nodes are located on a grid consisting of perpendicular line-segments. The performance of the proposed near-optimal and distributed algorithms tend to be closer to the optimal solution for larger networks.