Maximizing the overall end-user satisfaction of data broadcast in wireless mesh networks

We study the problem of broadcasting a common, possibly large, content into a wireless mesh network consisting of N end-users and of one or multiple access points that act as gateways to Internet. Each end-user is characterized by a maximum possible reception rate that depends on the distance and on the interface used to communicate with the associated access point. The end-user satisfaction is proportional to the actual rate received. The overall end-user satisfaction is the sum of the satisfaction of each end-user. Our goal is to maximize the overall end-user satisfaction under the constraint that the access points can retransmit at different rates the same common content at most K times. We show that the problem can be solved by serving the end-users according to a suitable K segmentation, which is a K partition of the end-users that preserves a specific end-user order. When the access points and the end-users have a unique interface, the optimal segmentation can be found in O(N(K+log⁡N)) time by exploiting the convex Monge property of the satisfaction function. When both access points and end-users are equipped with multiple interfaces, the problem becomes computationally intractable, even for a single access point. Polynomial time algorithms are then devised for optimally solving some meaningful particular cases.