Estimating the Cardinality of a Mobile Peer-to-Peer Network

Collecting information from mobile peer-to-peer (P2P) networks has important civilian and military applications. One problem is to determine the cardinality, i.e., the number of nodes, in a large mobile system. In a stationary wireless network, it can be trivially solved through a flooding-based query. However, the problem becomes much more challenging for mobile P2P networks whose topologies are constantly changing. In this paper, we present two novel statistical methods, called the circled random walk and the tokened random walk, to address this interesting problem. The circled random walk is simpler to implement and works well in networks of high mobility, whereas the tokened random walk works well with high or low mobility. These methods provide cardinality estimation by involving only a small subset of the nodes. They make tradeoff between overhead and estimation accuracy. The estimation error can be made arbitrarily small at the expense of larger overhead.