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

技术正在以惊人的速度发展，不久我们将不得不面对如何充分利用这一新兴技术的全新数学挑战。 一个非常真实的可能性是部署“智能灰尘”，即一个庞大的无线电收发器网络，以便监测大片地区，并可能跟踪该地区的动向。 这种“智能尘埃”只有在各种收发器非常便宜、使用很少的能源、能够使用很长时间并且安装成本不高的情况下才有用处。 特别是，不能期望收发器能够远距离传输，并且必须放置在基本上随机的位置。 这就引出了许多数学问题，我们希望解决其中的几个问题。例如，许多现实问题之一的数学模型如下所示。 假设我们在一个正方形或圆形圆盘上有大量随机分布的点（无线电收发器）。 设N是通过将每个点连接到离它最近的k个点而获得的网络（每个收发器可以与离它最近的k个收发器通信）。 为了使网络N连通，k应该有多大？ 换句话说，k应该有多大才能使得对于任何两个收发器x和y，消息可以经由收发器序列从x发送到y，即，存在收发器A、B、.，u，使得消息可以从x发送到a，从a发送到B等，最后从u到y。还有许多其他的数学问题与adhoc无线网络有关：例如，在上面的问题中，我们可以放松整个网络被连接的要求，并且只想要能够彼此通信的收发器的大集合。 关心消息传输到远方收发器的速度也是有意义的，我们可能想研究如何识别有效的路由。 在另一个问题中，我们应该考虑到如果几个附近的收发器同时广播所遇到的干扰。上述问题属于随机几何图理论，这是吉尔伯特大约45年前开始的一个领域，但奇怪的是，仍然没有太好的发展。 我们在这个NSF项目的目的是确定一些问题，不仅是从纯数学的角度来看的兴趣，但也有大量的应用程序，大型ad hoc无线网络。

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.