Collaborative Research: Applications of Random Geometric Graphs to Large Ad Hoc Wireless Networks

点击翻译按钮获取中文摘要

Technology is developing at a tremendous rate, and it will not be long before we shall have to face entirely new mathematical challenges as to how to make good use of this emerging technology. One of the very real possibilities is the deployment of `smart dust', a vast network of radio transceivers, in order to monitor large areas and, possibly, track movements in that area. Such `smart dust' is of any use only if the various transceivers are very cheap, use very little energy, so that they are around for a long time, and do not cost much to put in place. In particular, the transceivers cannot be expected to be able to transmit far, and must be placed in essentially random positions. This leads us to numerous mathematical problems, several of which we hope to attack.For example, a mathematical model of one of many real-life problems goes as follows. Suppose we have a large number of points (radio transceivers) in a square or circular disc, distributed at random. Let N be the network obtained by connecting each point to the k points nearest to it (each transceiver can communicate with the k transceivers nearest to it). How large should k be in order to make it likely that the network N is connected? In other words, how large should k be to make it likely that, for any two transceivers x and y, a message can be sent from x to y via a sequence of transceivers, i.e., there are transceivers a, b, ... , u, such that the message can be sent from x to a, from a to b, etc., and finally from u to y.There are numerous other mathematical problems related to ad hoc wireless networks: for example, in the problem above we may relax the requirement that the entire network be connected, and want only a large set of transceivers that can communicate with each other. It also makes sense to care about the speed with which a message can be transmitted to faraway transceivers, and we may want to investigate how an efficient route can be identified. In yet another problem, we should take into account the interference encountered if several nearby transceivers broadcast at the same time.The problems above belong to the theory of random geometric graphs, an area started by Gilbert about 45 years ago, but, curiously, still not too well developed. Our aim in this NSF project is to identify a number of problems that are not only of interest from the point of view of pure mathematics, but also have substantial applications to large ad hoc wireless networks.