The Protocol Engineering Research Center (PERC) is a DoD Multidisciplinary University Research Initiative (MURI) project funded by the US Air Force/OSR under Grant No. F49620-00-1-0330.
The PERC is a community of researchers from UC Irvine, UC Davis, UC Santa Barbara, UC Santa Cruz, Stanford University, and the University of Illinois at Urbana Champain. Their research focuses on network protocols, on their design, on their implementation, on analysis and verification tools and on middleware that allow users to make more effective use of network protocols, with a strong emphasis on building systems for the real world.
The main web page of the PERC describes the research of all the PERC participants.
The progress report describes the results obtained by PERC researchers during the first two years of the project.
The members of the PERC include some the world's leading experts in fault tolerance, real-time, wireless and mobility, and security. It also has great strength in network protocol infrastructure, networking middlewarer, and in design, analysis and verification tools.
At the University of California, Santa Cruz (UCSC), this project is part of the research carried out within the Computer Communication Research Group (CCRG) of the Baskin School of Engineering.
The principal investigator of this project at UCSC is J.J. Garcia-Luna-Aceves.
This is a presentation given at the PERC progress review
meeting held at UCSB on August 18-19, 2002:
powerpoint
At present, protocols to support wireless networks and mobility present the greatest challenge. Bandwidth and reliability are low, topology changes are frequent, and disconnection is common. The self-configuring, dynamic-connectivity, multihop-propagation and fully-distributed nature of ad-hoc networks make them very attractive for many Department of Defense projects but also introduce difficult problems at the link and network layers that need to be solved for multimedia and real-time applications to function across them. The scope of this part of the PERC is to investigate new link- and network-level protocols that can support ``QoS on the move'' and enable the seamless interconnection with the wired Internet.
The methodology for our work consists of verifying the correctness of the new algorithms and protocols, analyzing their performance through analytical models and simulations, and showing a selected subset of the protocols in working prototypes. To expedite technology transfer to the rest of the research community, we will carry out our simulations in GloMoSim and ns2, which is used widely in the research community. The simulation code developed at UCSC in the PERC is available to all PERC members and can be made available to interested parties outside the PERC.
The specific research areas of this component of the PERC are:
The results from the research carried out in the PERC have direct applicability to the development and implementation of much needed solutions in support of wireless internetworking solutions that are critical for a full-spectrum dominance in the battlefield by the U.S. forces. Lessons learned in the Task Force XXI experiments indicate that using COTS Internetoworking solutions will not suffice to satisfy the communication needs of military networks.
We are sharing many of the results developed with support from the PERC with Raytheon, which is applying the results to tactical wireless networks with multi-beam antennas as part of the DARPA FCS program.
The research being done in this component of the PERC is part of the thesis research of three of Ph.D. students.
With the support from AFOSR, we have written one book chapter, one journal paper, and 11 conference papers that have been accepted for publication. One of our papers is part of the program of ACM Mobicom 2002, which is the premiere international conference on mobile computing and networking, and this year accepted only 28 papers out of 289 submissions; and two of our papers are part of the program of IEEE ICNP 2002, which this year accepted only 32 papers out of 217 submissions.
We have developed the first analytical model for collision avoidance protocols with omni-directional transmission mode, all-directional transmission mode, and combinations of both. This work extends the analytical model first introduced by Takagi and Kleinrock for the analysis of CSMA in multi-hop networks with omni-directional transmissions. Extensive simulations in GloMoSim of the popular 802.11 MAC protocol and variants of it have been used to validate the analytical model. The results show that the overall performance of the sender-initiated collision avoidance scheme degrades rather rapidly when the number of competing nodes allowed within a region increases, in contrast to the case of fully-connected networks and networks with limited hidden terminals reported in the literature. We have also extended this model to networks with directional antennas. The collision-avoidance scheme based on directional handshakes and data transfer was shown to achieve much better spatial reuse (thus higher throughput) and less time in waiting (thus less delay) at the expense of higher collision rate.
We have started to analyze the interaction between broadcast and unicast traffic in multihop networks that use collision avoidance for channel access.
We designed and analyzed a new family of channel access protocols based on dynamic transmission scheduling. These protocols establish node-activation and link-activation schedules at each network node based on the identifiers of those nodes in the two-hop neighborhood of the node running the protocol. The Hybrid Activation Multiple Access (HAMA) protocol was introduced, which is the first known channel access protocol capable of establishing dynamically node- and link-activation schedules for both broadcast and unicast traffic. HAMA is remarkably simple, requires only two-hop neighborhood information, and avoids the complexities of prior conflict-free scheduling approaches that demand global topology information. We have also specified and analyzed a neighbor protocol for coordinating two-hop neighbor information in networks with dynamic topologies. The performance of HAMA was compared by analyses or simulations with that of idealized CSMA and CSMA/CA, dynamic scheduling based on node activation, and UxDMA. The results of our analyses clearly show that HAMA is far more effective than CSMA, CSMA/CA and scheduling based on node activation, and that it renders comparable performance to that of UxDMA without requiring to maintain complete topology information at each node.
We also introduced the receiver-oriented multiple access (ROMA) channel access scheduling protocol for ad hoc networks with directional antennas. Unlike random access schemes, ROMA determines a number of links for activation in every time slot using only two-hop topology information without complex handshakes or signal scanning to resolve communication targets. Exploiting the multiple directional beam forming capability of directional antennas in both transmission and reception, we have shown that significant improvements on network throughput and delay can be achieved.
We developed node-centric approaches to hybrid routing for ad hoc networks in which normal nodes are distinguished from special nodes, called netmarks, hosting popular network services or functioning as points of attachment to the Internet. With node-centric hybrid routing, netmarks force other common nodes to maintain routing information for them by either advertising their routing information as in table-driven routing protocols, or by requiring nodes to maintain routing entries towards them for extended periods of time. This reduces the network-wide flooding and the corresponding delay for route set up every time a session needs to be established between a normal node and a netmark. Routes between peer nodes are set up on-demand. Two node-centric routing solutions were developed based on partial link state information. One solution, called NEST, maintains table-driven routing for netmarks and on-demand routing is supported for common nodes. Simulation results using ns2 show that NEST performs much better than on-demand routing protocols based on distance vectors, path information or link-state information.
We developed a new routing metric, called the energy drain rate, which can be used as part of the route selection mechanism in routing protocols for ad hoc networks in order to preserve the remaining battery life of untethered nodes.
Lichun Bao and Soumya Roy successfully advanced to candidacy and are expected to graduate during the Fall 2002 quarter. J.J. Garcia-Luna-Aceves was Program Co-Chair of the ACM MobiHoc 2002 Conference, held in Lausanne, Switzerland on June 9--11, 2002.
To date, the majority of our progress has been on channel access. Our research over the next year focuses on the following areas:
Channel access: The remaining limitation of the channel-access protocols based on transmission scheduling that we have developed is that a node is given the opportunity to transmit independently of whether or not the node has something to transmit. We will work on flow-oriented scheduled channel access, which extends our prior results on scheduled channel access by using the flows traversing network nodes the entities that compete for scheduled channel access. We will also work on the characterization of flows over multihop networks that use collision avoidance in order to understand the fairness of such schemes and their ability to support higher-level protocols (e.g., routing) aimed at providing QoS guarantees.
Routing and multicasting: We will introduce QoS constraints into our partial link-state routing approach, and develop a mesh-based multicast protocol that supports QoS constraints. The goal of our multicast approach is to work correctly with on-demand and table-driven routing schemes.
Topology management: In contrast to a wired network, the scheduling decisions made at the MAC layer in wireless networks impact the de-facto topology over which routing and multicasting must operate. Hence, it is important to understand the ability to manage the useful topology of a wireless network to make network-level and end-to-end protocols more effective in multihop wireless networks. We will investigate topology management algorithms that build and maintain a virtual overlay topology based on the minimum dominating set (MDS) of the network. Our intent is to improve over the state-of-the art by developing heuristics based on two-hop neighborhood information already used for channel access.
We anticipate that Lichun Bao and Soumya Roy will complete their Ph.D. theses this year, and that Yu Wang will advance to candidacy during the Fall quarter. Lichun Bao, Soumya Roy, and Yu Wang will present papers at ACM Mobicom 2002, IEEE/ACM MASCOTS 2002, IEEE SAWN 2002, IEEE ICCCN2002, and IEEE ICNP 2002.
We will work with Raytheon to apply our results on channel access, routing, and multicasting to ad hoc networks based on untethered nodes with directional antennas.