Minimum energy multicast/broadcast routing with reception cost in wireless sensor networks

In this paper, we study the minimum energy multicast/broadcast problem with reception cost in wireless sensor networks. Suppose there are n sensors in the network. Each node v has l(v) transmission power levels to choose and its reception cost is B(v) if it receives a message. The problem of our concern is: given a multicast (broadcast) request, how to find a multicast (broadcast) tree such that the total energy cost of the multicast tree including transmitting cost and reception cost is minimized. There are two cases for reception cost: one is that for any node v, the reception cost of v only relies on v itself and is irrelevant with its transmitting node, the other is that the reception cost of v relies on not only itself but also its transmitting node. For the first case, we firstly propose a general approximation algorithm MEB-R-G for the broadcast problem. Moreover, for the multicast problem, we propose a general algorithm MEM-R-G and prove its approximation ratio, we also present a greedy algorithm. For the second case, we also propose a general approximation algorithm MEM-RT-G, and prove its approximation ratio.