Search

In this paper we address the problem of estimating the number of stations in a wireless network. Under the assumption that each station can detect collisions, we show that it is possible to estimate the number stations in the network within a factor 2 from the correct value in time O(log n log log n). We further show that if no station can detect collisions, the same task can be accomplished within a factor of 3 in time O(log2n) and maximum energy O(log n) per node, with high probability. Finally, we present an algorithm that computes the minimum value held by the stations in the wireless network in time O(log2n).

We study network load games, a class of routing games in networks which generalize selfish routing games on networks consisting of parallel links. In these games, each user aims to route some traffic from a source to a destination so that the maximum load she experiences in the links of the network she occupies is minimum given the routing decisions of other users. We present results related to the existence, complexity, and price of anarchy of Pure Nash Equilibria for several network load games. As corollaries, we present interesting new statements related to the complexity of computing equilibria for selfish routing games in networks of restricted parallel links.