The Complexity of Data Aggregation in Directed Networks
Consider a wireless network comprising two base stations, transmitting at high power, and an unknown number of client devices which communicate only with the base stations. The base stations are received at all devices, and each client device is received by at least one base station. However, due to power constraints, the clients are not necessarily received at both stations. The bandwidth of each base station is limited, allowing it to send only a certain number B of bits per timeslot. How many timeslots are required for the base stations to determine the approximate number of clients? The authors study this problem and other data aggregation problems in directed networks, where communication is not necessarily bidirectional.