Bell University Laboratories

Bell University Laboratories

at the University of Waterloo

GRANT APPLICATION FORM

1a. Title of Proposal

MAC and routing for multihop mesh wireless networks

1b. Funding Category

Seed Project - Early investigation in a given research area (max. $25K/yr.). / x / Mission Oriented Research - research is aimed at an existing or potential Bell initiative. Requires Bell Champion.

1c. Principal Investigator

Principal Investigator / Department of primary appointment / Administering Unit if different from Dept.
Catherine Rosenberg / Electrical and Computer Engineering
% of Research Time / Personnel # / Phone / Fax / E-mail
15% / 519- 888 4016 / 519 746 3077 /
Appointment Status
x / Tenured / Tenure Stream / CLTA / Status Only / Other:

1d. Other Team Members

Faculty Co-Applicants / Department of primary appointment / % of Research Time
Prof. Ravi Mazumdar / Electrical and Computer Engineering / 15%

1e. Primary Bell Champion

Contact / Business Unit
Dr. Aladdin Saleh / Bell/Wireless Technology Strategy
Title / Phone / Fax / E-mail
Associate Director / 905-282 3264 / 905-282 3337 /

1f. Second Bell Champion

Contact / Organization
Title / Phone / Fax / E-mail

1g. Length of Project and Funding Requested

Length of Project / Year 1 / Year 2 (Projected) / Year 3 (Projected)
2 years / $ 120,382 / $ 120,382 / $

Note: The funding period for a successful project will not exceed a period of one (1) year - projected funding for subsequent years is just an indication of the future scope of the project and the likely amounts that will be requested for renewal.

1h. Location of Research (if more than one research location, please specify primary location

University of Waterloo

1i. Investigators' Undertakings

1. It is agreed that the conditions governing grants as outlined in the Research Project Agreement, including the attached Confidentiality Terms and Conditions, attached apply to any grant made pursuant to this application and are hereby accepted by the applicant.
2. The research shall be performed and administered in accordance with the general conditions governing grants as outlined in the Research Project Agreement, including the attached Confidentiality Terms and Conditions.
3. All staff and students engaged on the project shall be fully informed of, agree to be bound by and execute, the Participant Agreement, including the Confidentiality Terms and Conditions attached thereto.
4. Any research involving the use of human subjects, animals, biohazardous agents or radioactive materials will not be undertaken without the prior written approval of the appropriate University committee.

______March 30, 2006______
Principal Investigator SignatureDate
The faculty co-applicants agree to the above conditions and further agree that the Principal Investigator shall administer the grant on behalf of the group.
Prof. Ravi Mazumdar______March 30, 2006______
NameSignatureDate
______
NameSignatureDate
______
NameSignatureDate

1j. Approval Signatures

Please provide signature of Chair/Director of the Principal Investigator’s department or school:

1. The undersigned certify that the principal investigator meets the eligibility requirements, as outlined in Appendix A of this application form.
2. The Department/School shall provide the Principal Investigator with the space and basic facilities to carry out the research.
3. The Department/School shall notify their BUL contact of any change in the status of the Principal Investigator during the tenure of the grant.

______
NameSignatureDate
______
Title Department/School
Research Services Approval (To be signed on behalf of the University by a representative of the Office of Research at the University of Waterloo)
______
Name (I have the authority to bind the University)SignatureDate

Notes

1. Please attach brief CVs for the PI and co-applicants on the team, with content equivalent to NSERC Personal Data Form 100. See for sample forms.
2. Please submit this application, with original signatures, to your BUL contact. Also send an electronic copy of this application to your BUL contact.
3. If the research project requires an Ethical Review (see section 7), a separate ethical review form must also be attached to the application.

2. Bell Champion

This portion of the application form must be filled out by the championing group/organization and signed off by the appropriate business leader.

2a. Commercial Plans

Outline how the proposed research results will be applied to or impact upon current or planned Bell initiatives. Also outline how you plan to interact and coordinate with the proposed project. If possible, outline commercialization plans for results from the research.

There is an increasing demand for broadband access. Service providers including Bell are looking for different technologies and configuration to deliver high bandwidth using the most optimal solution. The IEEE 802.16 is one such protocol envisaged to provide broadband wireless access. Bell has already considered introducing this technology into its network. This technology with its optional mesh networks configuration is expected to increase the reach of the network by increasing the area over which of access is possible. While the standard defines most of the technical specifications, it has given very little specification of the MAC layer and the routing structures. However, proper design of the MAC layer and routing is critical for achieving high user level QoS (Quality of Service). Given the dynamic nature of channel conditions one needs to optimize the MAC to take into account these variations and reduce interference from other users. Such schemes are called opportunistic.
The proposed research will build upon earlier work of the PI’s in the first phase of the BUL supported grant where they studied the issue of MAC in different wireless networking scenarios. In a year, the team has produced fundamental results as well as proposed new protocols and developed a comprehensive optimization framework to design future solutions. The team has been able to leverage the BUL funding to obtain NSERC CRD funding that is guaranteed for 3 years subject to BUL commitments. This has allowed the PI’s to build critical strength in the research effort to provide answers to the issue of ubiquitous broadband wireless access. In the next phase will study how a distributed MAC and routing scheme can be designed in conjunction to approach the performance bounds of a mesh network. Success in this phase will provide means to deploy robust and efficient mesh networks that will provide a much larger footprint for broadband wireless access in urban environments and this will have immediate advantage to Bell.

2b. BELL Commitment (Signoff by appropriate business leadership)

Please provide the signature of the champion’s business leader
The undersigned certifies support for the attached proposal within the scope of his/her mandate. The aforementioned Bell Champion will be the primary point of contact within Bell for this project. Further, the Bell Champion accepts responsibility for Bell’s commitments to the project as deliverables of their business unit.
______
NameSignatureDate
______
Title Department

3. Description of Proposed Research

3a. Introduction and Overview

Providing ubiquitous broadband wireless access in the last mile is now the last phase of the wireless revolution but one that will be lucrative and of strategic interest to Bell in order for it to provide end-to-end wireless connectivity. However at the present time broadband wireless access is in its very early stages. With the improvements in the infrastructure and the rapid increase in bandwidth consuming applications it is necessary to begin the deployment of the next generation of wireless access that will not only provide bandwidth but will maximize the number of users in the system.
One of the key issues in wireless access is the issue of MAC (Medium Access Control) [IR06] that is related to how users access the channel. There are essentially two approaches: one is via a contention based scheme like in the IEEE802.11 that is appropriate for LANs while the second is a scheduled or coordinated access based on a TDMA (Time Division Multiple Access) that apportions parts of time slots to one or many users. The second approach provides higher bandwidths that can be enhanced by taking advantage of channel and interference conditions, commonly referred to as opportunistic scheduling. This is better suited to an infrastructure based network such as Bell might deploy in the urban environment. In the first year of BUL funding we studied the issue of MAC in multihop networks and showed how existing protocols fare in different scenarios [IR06]. We also proposed a very simple and robust MAC protocol and started to study the interplay between MAC and resource allocation (power, modulation, etc.) in a multihop setting. The proposed work will build upon these results to investigate how routing interact with MAC in the context of mesh networks that are of commercial importance to Bell. It is important to note that we were able to leverage the BUL funding to obtain a NSERC CRD grant to comprehensively study the issues related to providing broadband wireless access.
The last year has seen an increasing amount of deployment of wireless hot spots and access points in urban areas. This has given rise to so-called mesh architectures that are multi-hop wireless networks that are infrastructure based. They will provide wireless connectivity over a much larger geographical area than their single-hop counterparts.
Developing a MAC in such a setting is very closely tied to the routing (the actual links that are activated). In preliminary work carried out in the first part of the project we showed that such problems lead to very special matching problems that depend on the power, modulation, and channel conditions. These matching problems are in general hard to solve. The IEEE 802.16 (WiMax) that has been proposed as the standard for wireless access allows for the use of multiple modulation schemes (rates), powers, etc. Thus it is essential to study the tradeoffs between the complexity of the MAC/routing and the efficiency that might be gained by using the larger set of parameters to optimize over. Thus the research we propose in this phase is the following: 1) Understanding and formulating the appropriate optimization problems for resource allocation in networks that necessarily includes MAC and routing and a realistic physical layer model; 2) Develop so-called polynomial approximations so that the network can obtain the MAC and routing scheme in real time when channel conditions and user characteristics vary; 3) Characterize the sustained average saturation throughput for contention based schemes. Characterizing this will enable performance guarantees to be given by the operator.
These results are necessary for the deployment of efficient mesh networks and to enable a provider like Bell to advertise performance guarantees or advantages.

3b. Summarize current state of the art in the general area of the proposed research

In the first phase of the research we concentrated our effort on understanding the problem of the interplay between the MAC, resource allocation, and determining the capacity of wireless links under an interference constraint. The very concept of link capacity, though obvious for wired links, is difficult to define for wireless links in a network. In fact, whether a link can be associated with a number denoting its link capacity depends on how the interference due to other transmitting devices in the network to the transmissions on the link is managed. In networks which employ randomized MAC protocols such as IEEE802.11, assigning capacities to individual links is very difficult. This means that in such wireless networks, the issue of how much traffic a link can carry (the rate allocation) cannot be simply cast as that of dividing individual link capacities, as in the wired networks, and hence developing efficient routing strategies on these networks is very hard.
With the advent of software controlled radios, modifying the radio transmission parameters (e.g., transmission power, modulation/FEC schemes, back-off parameters, etc.) ``on the fly" will become possible. Since the traffic carrying capacity of a wireless network is determined by these parameters, this essentially means that, rather than taking the network capacity as fixed and given, it can be dimensioned dynamically, i.e., at the time-scale of rate allocations by varying the ``network parameters''. Thus in contrast to the wired networks, in which perhaps the only way to change network capacity is to revamp the infrastructure, a wireless network can potentially be “fitted'' to its environment and users.
Wireless technologies have evolved in such a way that it is possible to deploy and operate wireless networks in two significantly different ways, in a contention or random access mode that is easily decentralized or in a scheduled manner that is more suited to infrastructure based networks. Infrastructure-based networks are those with proper infrastructure (subscriber stations, access points, etc.) deployed with the intent of providing backbone service to the users; the prime example being IEEE 802.16 based broadband mesh wireless networks. In these networks, the networking functionality will be built into the network devices whereas the applications running on user devices will act as the end users. In view of the previous point, this permits the network and the users to be seen as separate optimizing entities influencing the rate allocations and network dimensioning through mutual interaction. However
This still poses challenges because devising MAC schedules means that centralized coordination is needed and that is very complex to implement. In our research we will look at both the centralized MAC scheduling or a distributed random access based MAC- the tradeoffs are not clear because one offers the possibility of greater efficiency but at a greater complexity and thus is less robust.
As a consequence of these, interesting difficulties as well as possibilities are opened up in formulating and solving the rate allocation problem in the context of multihop wireless networks. This has two ramifications. First, owing to the separation of the network and the users, network dimensioning in response to user rate requirements and vice versa is not a ``cross-layer optimization'' issue; this allows us to include any protocol parameters (amenable to ``on the fly” modification) affecting the network capacity in our formulations. This is in contrast to the earlier works [YS05], [XLN05], [LS05], and [C05]) which have invariably focused on the ad hoc networks and cross-layer optimization (TCP-MAC, TCP-PHY) where it is assumed that somehow a suitable MAC schedule is available. Secondly, in an optimization context it allows the users to be seen as consumers, their data rates as produced commodities, the network as a producer and the protocol parameters as factors of production or input commodities.
The performance of these networks depends critically on the design of the underlying MAC protocols. Even though there is a wealth of literature devoted to MAC protocols and their associated problems, the understanding of the relative importance of these problems and their interaction with rate allocation is still quite limited. This is because most of the previous work focuses either on designing collision avoidance mechanisms to ``solve'' particular problems, or on identifying scenarios where a particular MAC protocol, usually IEEE 802.11, does not work well. In addition, most of the work on designing collision avoidance mechanisms, is based on simplistic assumptions about the physical wireless medium, like a fixed communication range and a fixed interference range. The problem is that in a multihop setting they cannot be studied in isolation. In [KMR06-1] we have shown that even under the simplifying assumption of fixed powers and modulation schemes, the capacity that can be associated with a link and the MAC need to be solved together. This results in a so-called matching type of problem based on a contention graph that dictates links that are in conflict if a particular link is chosen and those on which simultaneous transmissions can go on.
This brings up the issue on the structure of the matching algorithms. In simple cases of power sufficient to interfere with a two hop neighbourhood the matching problem can be solved in polynomial time. However if we wish to exploit the power control available to increase link rates then the matching problem becomes extremely hard to solve, indeed it is NP hard [SMS06]. We thus need good approximation algorithms. However, since we have now developed the appropriate framework in our research to address these problems we will focus our attention in the proposed research to adapt the methodology and algorithms to address the characterization of the achievable rates in the multihop mesh networks and devise distributed (node based with local communication) algorithms to achieve them

3c. Detailed Description of Research - include motivation, intellectual uncertainties, relationship with other work in the field, how it differs or adds to current state of the art. Where appropriate, discuss research methodologies and rationale. Please limit your response to 2 pages. If further explanation is deemed necessary, please include it as an appendix.

The goal of this phase in our research is to develop models, optimization frameworks, and algorithms to deploy wireless mesh networks in an urban setting where there are varying channel conditions due to user interference and mobility. The research we propose in this phase will focus on the maximizing achievable rate allocation to wireless links that takes into account the network resources (power, rates, etc), MAC scheduling and routing strategies for efficient transmissions between nodes to the wireless routers. The research will involve the following critical steps: 1) The formulation of the joint allocation and MAC scheduling optimization; 2) Determining the routing strategy for throughput maximization ; 3) Developing distributed rate allocation algorithms; 4) Developing polynomial time approximations to solve the matching problems; and 5) Determining the saturation throughput in mesh networks given that users will either use contention based or TDMA schemes for accessing the uplink.
Although we have stated the above as different problems, in the context of mesh networks it is only by treating all these issues in a unified way can one hope to design efficient networks.
The basic issue in all these problems is assigning a throughput capacity to the links. What differentiates a network of wired links and that of wireless links is the fact that the link capacity of a wired link is invariant to what transpires on the other links in the network whereas such is not the case for a wireless link owing to the inherent broadcast nature of the wireless medium. This means that transmissions on a link, which otherwise would have been successful, may fail due to interference from other simultaneous transmission(s) on the links in its vicinity. This necessitates some sort of coordination among the wireless links. If this coordination is achieved through a pre-computed (i.e., independent of the traffic being carried by the links), conflict-free (i.e., whenever a link transmits, it can transmit successfully) link transmission schedule, then it is possible to assign each link a capacity. This link capacity, obviously not exceeding that ``in isolation'', is simply the link capacity in isolation multiplied by fraction of time allocated to the link for transmission in the schedule. This results in a classical optimization framework which is well understood in terms of so-called primal-dual algorithms that can be adapted from the wireline network context [KMT98]. However, the possibility of dynamic configuration of parameters as in IEEE 802.16 Mesh networks with centralized scheduling, allows the link constraints to be seen as parameterized by the transmission schedule and PHY parameters. This allows us to achieve higher efficiencies but requires much more sophisticated algorithms. In [KMR06-1] we have shown that when the contention graph is a singleton that occurs when the transmitting powers are sufficiently low or the maximum rate constraints are high [LMS06], the optimization problem results in a very special solution that yields both the optimal rates on links and the MAC schedule that depends on the traffic. Knowing this structural result then allows us to find the optimal node configuration (which link connections must be activated) and the routing strategy to maximize the throughput or achievable rates that can be sustained in the network. For a grid topology with the sink in a corner, and all the nodes using the same radio parameters, we obtain [KMR06-2] the maximum throughput in a closed form under a two-hop interference model. The optimal routing is such that in a certain region around the sink the traffic is routed using the shortest paths while the traffic outside this region flows in two branches deviating away from each other and finally getting fed into the region through the border nodes. Interestingly, of all feasible transmission powers, the power which allows sensors to transmit to the sink in one hop has the maximum throughput. The importance of this result is that the results are not of an asymptotic nature but are exact.