2017/01/15 by Rajat Talak, Talak, Rajat, Sertaç Karaman +3
Computer Science · #Opportunistic and Delay-Tolerant Networks #Cooperative Communication and Network Coding #Mobile Ad Hoc Networks
paper · pdf · doi:10.48550/arxiv.1701.04130
We study broadcast capacity and minimum delay scaling laws for highly mobile\nwireless networks, in which each node has to disseminate or broadcast packets\nto all other nodes in the network. In particular, we consider a cell\npartitioned network under the simplified independent and identically\ndistributed (IID) mobility model, in which each node chooses a new cell at\nrandom every time slot. We derive scaling laws for broadcast capacity and\nminimum delay as a function of the cell size. We propose a simple\nfirst-come-first-serve (FCFS) flooding scheme that nearly achieves both\ncapacity and minimum delay scaling. Our results show that high mobility does\nnot improve broadcast capacity, and that both capacity and delay improve with\nincreasing cell sizes. In contrast to what has been speculated in the\nliterature we show that there is (nearly) no tradeoff between capacity and\ndelay. Our analysis makes use of the theory of Markov Evolving Graphs (MEGs)\nand develops two new bounds on flooding time in MEGs by relaxing the previously\nrequired expander property assumption.\n