In this paper, we propose solutions for the minimum-energy broadcasting problem for cross networks, where N nodes are located on two perpendicular lines. Our solutions consist of an algorithm which finds the optimal assignment in polynomial time, a near-optimal algorithm with less complexity (O(N)), and a distributed algorithm with complexity O(1) that gives acceptable results. 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). The results show that while the proposed optimal algorithm finds the best solution, our near-optimal algorithm performs better than BIP in all cases, and the distributed algorithm performs close to it. The performance of our non-optimal algorithms tend to be closer to the optimal solution for larger networks. We prove that all the algorithms perform the same in the asymptotic regime.

Additional Metadata
Keywords Broadcasting, Cross Networks, Energy Consumption, Transmission Range Assignment, Wireless Ad-Hoc Networks
Persistent URL dx.doi.org/10.1109/ICC.2015.7249373
Conference IEEE International Conference on Communications, ICC 2015
Citation
Ataei, M.R. (Mohammad R.), Banihashemi, A, & Kunz, T. (2015). Minimum-energy broadcasting for cross wireless ad-hoc networks. Presented at the IEEE International Conference on Communications, ICC 2015. doi:10.1109/ICC.2015.7249373