Low Complexity Algorithm for Efficient Relay Assignment in Unicast/Broadcast Wireless Networks

Using relayers in wireless networks enables higher throughput, increased reliability or reduced delay. However, when building networks using commercially available hardware, concurrent transmissions by multiple relayers are generally not possible. Instead one specific relayer needs to be assigned for each transmission instant. If the decision regarding which relayer to assign, i.e., which relayer that has the best opportunity to successfully deliver the packet, can be taken online, just before the transmission is to take place, much can be gained. This is particularly the case in mobile networks, as a frequently changing network topology considerably affects the choice of a suitable relayer. To this end, this paper addresses the problem of online relay assignment by developing a low-complexity algorithm highly likely to find the optimal combination of relaying nodes that minimizes the resulting error probability at the targeted receiver(s) using a mix of simulated annealing and ant colony algorithms, such that relay assignments can be made online also in large networks. The algorithm differs from existing works in that it considers both unicast as well as broadcast and assumes that all nodes can overhear each other, as opposed to separating source nodes, relay nodes and destination nodes into three disjoint sets, which is generally not the case in most wireless networks.