Workshop Proposal on Theoretical Aspects of Wireless Ad Hoc Networks

随着Napster的兴衰，\emph{点对点} （P2P）这个术语开始被公开使用。尽管在分布式计算的进化阶段已经有了更早的系统，P2P系统第一次作为一个重要的社会和技术现象出现是在Napster的部署之后。目前大多数流行的P2P系统都是针对文件共享应用，文件存储在一些终端用户的机器上，而不是传统的客户机/服务器模式的中央服务器上。无线自组织网络只是P2P网络的一种特殊情况，不需要基础设施或蜂窝网络进行通信。近年来，人们对无线自组织网络进行了大量的研究。这些作品涉及计算机科学的许多理论方面，包括近似算法，计算几何，组合学，分布式算法。然而，无线广告网络仍然面临着许多挑战。由于处理能力、存储能力和能量供应的限制，许多传统算法过于复杂，无法在无线自组织网络中实现。其他一些算法没有利用无线网络的几何特性。此外，目前开发的无线网络算法大多假设每个无线节点的精确位置，这在实际中是不可能的。在该领域开发的大多数算法也假设所有节点具有均匀传输范围。当节点的传输范围不一致时，这些算法可能会失败。此外，无线自组织网络需要低计算复杂度和低通信复杂度的高效分布式算法。这些算法有望利用无线自组织网络的几何特性。有几个基本的问题需要回答：我们能否在无线自组织网络下提高传统分布式算法的性能？无线节点的位置信息是否会影响算法的性能？我们建议组织一次研讨会，征求有关应对这些挑战的最新研究成果。具体主题包括但不限于以下问题：连接部署，覆盖部署，吞吐量，移动性，信道分配，功率/拓扑控制，本地化路由，合作执行和机制设计，安全性。许多来自国内外的初级教师和研究生一直在积极致力于解决这些挑战。他们将是本次研讨会潜在与会者的主要组成部分。该研讨会旨在将移动计算和分布式算法的研究人员聚集在一起，以促进合作。这将是一次生动的会议，涵盖该领域的许多算法和离散方面，从运筹学到无线电工程问题。它特别旨在促进该领域的实践者和理论家之间的合作。我们计划于2004年6月2日在伊利诺斯州的芝加哥举办这个研讨会。研讨会论文将发表在研讨会论文集上，选定的论文将发表在期刊的特刊上。通过组织关于无线自组织网络理论方面的研讨会，解决了一些挑战和基本问题。研讨会的潜在参加者将是在无线自组织网络理论方面积极工作的初级教师和高级博士研究生。因此，一个成功的研讨会将激发更多的初级教师和博士生在这一领域的研究。我们自己与博士生合作的经历非常好。我们目前支持的博士生已经在主要理论和/或网络会议上发表了相当多的论文。参加这个由美国国家科学基金会组织的研讨会将提高他们的生产力。由于建议的研究活动涉及理论理解和解决无线网络的实际问题，建议的研讨会将促进与其他学科的院系的合作，一些来自工业界的研究人员将在更实际的环境中验证已开发的理论方法，以观察其实际性能。此外，由于特设网络支持与救灾、公共事件协调以及军事和执法行动相关的应用，因此拟议的研究具有巨大的社会影响。

The term \emph{peer-to-peer}(P2P) came to the force very publicly with the rise and fall of Napster.Although there are prior systems in this evolutionary phase of distributed computing, P2P system first emerges as a significant social and technical phenomenon right after the deployment of Napster.Currently most of popular P2P systems are aiming at the file sharing applications, where files are stored at some end-users' machines rather than at a central server in the traditional client/server model.Wireless ad hoc networking is just a special case of P2P networking, where no infrastructure or celluar networking is needed for communication.Recent years saw a great amount of research in wireless ad hoc networks. Theseworks involve a number of theoretical aspects of computer science, includingapproximation algorithms, computational geometry, combinatorics, distributedalgorithms. However, there are still many challenges in wireless ad hocnetworks. Due to the limited capability of processing power, storage, andenergy supply, many conventional algorithms are too complicated to beimplemented in a wireless ad hoc networks. Some other algorithms did not takeadvantage of the geometry nature of the wireless networks. Additionally, mostof the currently developed algorithms for wireless networks assumed a preciseposition of each wireless node, which is impossible practically. Majority ofthe algorithms developed in this area also assume all nodes have uniformtransmission range. These algorithms will likely fail when nodes havedisparity transmission ranges.Furthermore, the wireless ad hoc networks requires efficient distributedalgorithms with low computation complexity and low communication complexity.These algorithms are expected to take advantage of the geometry nature of thewireless ad hoc networks. Several fundamental questions should be answered:can we improve the performance of traditional distributed algorithms underwireless ad hoc networks? Does the position information of wireless nodes makedifference in algorithms' performance?We propose to organize a workshop to solicit the recent research efforts onaddressing these challenges. Specific topics include but are not limited tothe following issues:Deployment for Connectivity,Deployment for Coverage, Throughput,Mobility,Channel Assignment,Power/Topology Control,Localized Routing,Cooperation Enforcement and Mechanism Design,Security.A number of junior faculty and graduate students from both domestic andinternational have been actively working on addressing some of thesechallenges. They will be the main component of potential attendees of this workshop.The workshop is intended to bring together researchers in mobile computing anddistributed algorithms to foster cooperation. It is intended to be a livelymeeting, covering many of the algorithmic and discrete aspects of this fieldgoing from operations research to radio engineering problems. It aims, inparticular, at fostering the cooperation among practitioners and theoreticiansof the field. We plan to hold this workshop on June 2nd, 2004 at Chicago,Illinois. Workshop papers will be published in workshop proceedings andselected papers will be published in a special issue of a journal.By organizing the workshop on the theoretic aspects of wireless ad hoc networks that addresses the a number of challenge and fundamental problems.The potential attendees of the workshop will be junior faculty and senir PhD students who had been actively working in the theoretic aspects of wireless ad hoc networks.Thus, a successful workshop will initiate more junior faculty and PhD students in the research of this area.Our own experiences in working with PhD students has been excellent.Our currently supported Ph.D. students have already contributed to considerable number of papers published in major theoretical and/or networking conferences.Exposure to this workshop organized by National Science Foundation will increase their productivity.Since the proposed research activities involve theoretical understanding and solving of practical questions from wireless networking, the proposed workshop will foster collaborations with faculties from other discipline, some researchers from industry to verify the developed theoretical methods in a more practical settings to see its practical performance.Additionally, since ad hoc networks support applications related to disaster relief, public event coordination, and military and law enforcement operations, the proposed research has vast societal impact.