[ Homepage  | Biography  | Courses  | Members  | Publications  | Research/Funding  | Workshops/Presentations  ]

Wireless, mobile, ad hoc and sensor networks

Ad hoc networking has been a dynamically growing research area for the last years. The need for a network when there is no infrastructure is no more limited under military and emergency applications; ad hoc networks can include private (ehome entertainment, business) and public (fast outdoor downloading) applications as well. In ad hoc networks, wireless mobile computing devices can perform critical network topology functions that are normally the job of routers within the Internet infrastructure. Keeping track of the connections between computers is something so basic that a computer network, almost by definition, cannot exist without it. Although there are many kinds of protocols available today that are supported by network infrastructure, they need adaptation before they can be useful within a network no longer connected to the Internet infrastructure. On the one hand, ad hoc networks might provide the basis for commercially successful products/applications (conferencing, home networking,emergency services, embedded computing applications, sensor networks). On the other hand, they suffer from some crucial disadvantages: the accidental nature of their deployment (high data loss probability), vulnerability to scalability problems (loss of aggregation leads to bigger routing tables), trade-off between power budget and latency, reduced wireless data rates, additional security exposure.

MAC protocols for wireless networks

In a wireless network, many users communicate over a shared channel. The call admission region and scheduling policies for a time division multiple-access wireless system supporting heterogeneous real-time variable bit rate applications with distinct quality of service (QoS) requirements and traffic characteristics have been determined. The call admission region has been established for policies that are work-conserving (WC) and that satisfy the earliest due date (EDD) service criterion (WC-EDD policies). Such policies are known to optimize the overall system performance. Scheduling policies that deliver any performance in the region established for WC-EDD policies have been constructed, whereas an upper bound on the call admission region that can be achieved under any policy (not limited to the WC-EDD policies) has been determined.

Besides, the minimum system dropping rate induced by time division multiple access (TDMA) schemes supporting time-constrained applications with common maximum cell delay tolerance has been determined. Expressions have been derived for the induced system dropping rate for various TDMA schemes with different overhead and the maximum number of users that can be admitted in the network without violating the maximum dropping rate constraint has been determined. The system dropping rate achieved by suboprtimal TDMA schemes has been compared against the optimal (although ideal) TDMA scheme performance. The performance limiting factors associated with the suboptimal schemes have been identified, and the magnitude of their (negative) impact has been evaluated. Based on this information it is possible to point to performance improving modifications which should be pursued to the extent permitted by technological constraints. Based on these derivations, a network designer may choose the best TDMA scheme to use in a particular situation.

Topology-unaware MAC protocols for ad hoc networks

The idiosyncrasies of the ad-hoc networks make the design of an efficient Medium Access Control (MAC) a challenging problem. These networks require no infrastructure and nodes are free to enter, leave or move inside the network without prior configuration. This flexibility introduces new challenges and several MAC protocols have been proposed that is possible to categorize them according to the scheduling of their transmissions.

The first category corresponds to MAC protocols that allow the users to content in order to transmit. Corrupted transmissions (collisions) are possible and the CSMA/CA-based IEEE 802.11, is a very well known example. Additionally to the carrier sensing mechanism, the Ready-To-Send/Clear-To-Send (RTS/CTS) handshake mechanism is mainly introduced to avoid the hidden/exposed terminal problem, which is a reason for significant performance degradation in ad-hoc networks.

The second category refers to TDMA-based MAC protocols where each node has been assigned a certain set of TDMA scheduling time slots that is allowed to transmit. In general, optimal solutions to the problem of time slot assignment often result in NP-hard problems, which are similar to the n-coloring problem in graph theory.

Topology-unaware scheduling schemes determine the scheduling time slots irrespectively of the underlying topology. Chlamtac and Farago, have proposed a TDMA-based topology-unaware scheme that exploits the mathematical properties of polynomials with coefficients from finite Galois fields to randomly assign scheduling time slot sets to each node of the network. For each node it is guaranteed that at least one time slot in a frame would be collision-free. Another scheme proposed by Ju and Li, maximizes the minimum guaranteed throughput. However, both schemes employ a deterministic policy for the utilization of the assigned time slots that fails to utilize non-assigned time slots that could result in successful transmissions.

In order to support network applications in highly-mobile environments, a topology-unaware scheme appears to be a suitable candidate. After an extensive study of the aforementioned topology-unaware schemes it was revealed that there exist unused resources that could be safely used to increase the throughput. This could be possible a) by allowing nodes to exchange their scheduling time slots and therefore decide which unassigned time could be used by each node or b) by allowing all nodes to use the unassigned time slots according to a common probability p which value could be determined. The former approach requires coordination among nodes and it is not a topology-unaware approach as the latter one.

Therefore, the Probabilistic Policy, capable of utilizing the non-assigned slots according to the access probability p, fixed for all users in the network, was introduced and analyzed. The conditions under which the system throughput under the Probabilistic Policy is higher than that under the Deterministic Policy (the one proposed by Chlamtac and Farago) were derived analytically for heavy traffic conditions. Further analysis of the system throughput was shown to be difficult or impossible for the general case and certain approximations were considered whose accuracy was also investigated.

The approximate analysis determined the value for the access probability p that maximizes the system throughput as well as simplified lower and upper bounds that depend only on a topology density metric. Simulation results demonstrated the comparative advantage of the probabilistic policy over the deterministic policy and had shown that the approximate analysis successfully determines the range of values for the access probability for which the system throughput under the probabilistic policy is not only higher than that under the deterministic policy, but it is also close to the maximum.

Further research work involves a study with respect to the load of the network (heavy traffic conditions were assumed so far), the power consumption under the Probabilistic Policy compared to the power consumption under the Deterministic Policy as well as the advantages when smart antennas are used. A new policy, the Adaptive Policy is currently under investigation and simulation results show that achieves throughput close to the theoretical maximum while the power consumption is minimized. Analysis results are expected to support the claims and expectations introduced by the simulation results for this new policy.

Routing in ad hoc networks

Despite the diversity of conditions that may be encountered in ad hoc networks, the research community has lacked sufficient depth of understanding of the limitations of current ad hoc routing protocols, and their dependence on interacting system parameters and environmental factors. As such, the majority of research focused on ad hoc network routing protocol design has resulted in strategies that are limited in practical terms to a narrow range of environments. The success of the technology, however, depends on the development of scalable routing algorithms that are capable of adapting efficiently to substantially greater variation in network size and range, as well as significant temporal and spatial variation in traffic and mobility patterns.

Engaging in a single ad hoc routing strategy is insufficient for effectively adapting to the wide range of environments present in such networks. Instead, a unified multi­mode routing strategy should be developed that applies the ``mode'' determined to be most effective at a given point in time and for the appropriate portion of the network. To achieve this objective, however, would require a deeper knowledge of the tradeoffs inherent in routing algorithm design and performance in dynamically changing environments than that available through the existing literature.

Several difficult challenges that facilitate the synthesis of a multi­mode routing framework have been addressed.

Specifically, a comprehensive analysis of simplified variants of ``limited'' link­state routing in the context of scalability demonstrates the impact of link­state dissemination policies on network performance. The results lead to the derivation of a novel algorithm, namely Hazy Sighted Link­State (HSLS) that is shown to provide an optimal balance between control overhead and route optimality.

An in­depth theoretical analysis of the asymptotic performance of a representative set of the fundamental classes of ad hoc routing protocols has been conducted with respect to traffic, mobility and size. The analytical results, which are the first of their kind, provide insight into the fundamental properties and limitations of ad hoc networks (limits, trade­offs, and behavior), and demonstrate the feasibility of utilizing HSLS, an easy­to­implement, low­overhead alternative to complex dynamic hierarchical schemes in order to achieve scalability.

Two novel enabling algorithms, namely, the Limited Link State (LLS) and Self­Organizing (SO) algorithms have been derived. Together, these algorithms can be combined into an effective multimode routing strategy that adapts to any ad hoc network condition -from small networks consisting of low mobility nodes to large networks of highly mobile nodes to heterogeneous networks consisting of different classes of users- in order to make the most efficient routing decisions. These algorithms employ novel metrics that capture the mobility and traffic pattern of a subset of the network. Based on the multi­mode framework, once the current local structure of the network is determined utilizing these metrics, the mode of operation can be shifted on a localized basis to that which is best suited for the environment.

Multi-hop extensions in WLANs

In urban deployments, where the number of users and the traffic needs are potentially high (hotspots), wireless local area networks (WLANs) appear to be a good candidate for a wireless bridge to the backbone network. The challenge is to make them adequate for supporting demanding future applications. The (infrastructure-based) WLANs allow for a centralized mode of operation, where the Access Point (AP) controls the transmissions inside its cell and provides for a single-hop network connecting Mobile Terminals (MTs) with the Internet. These networks provide for the extension of the fixed network infrastructure and the support of low data rates and they are simple and capable of providing - even rather limited - Quality of Service (QoS) guaranties. On the other hand, WLANs have short coverage (limited by single-hop communication), they do not support direct peer-to-peer communication and the AP may always be a throughput bottleneck for its cell.

The employment of the ad hoc networking paradigm into (infrastructure-based) WLANs has been motivated by the need to support high-rate applications, the capacity requirements in hotspots and the appeal of direct peer to peer communication between two MTs. It is basically introduced by reducing the transmission power of the MTs to decrease the transmission (communication) range and by allowing for peer-to-peer and multi-hop communication. The direct application of the peer to peer networking paradigm in a WLAN may lead to a substantially decreased throughput for the traffic directed to the AP. On the other hand, the cumulative receiving throughput of nodes located at the periphery of relatively small circular areas around the AP is expected to be substantially higher. Thus, the capacity of the multihop cellular network may be enhanced by employing the peer to peer paradigm only outside a circular area around the AP and the cellular paradigm inside this circular area.

The Centralized Ad-Hoc Network Architecture (CANA) has been proposed in order to allow for a dual-mode system based on HiperLAN/2. CANA introduces the ad hoc functionality of shorter-range communication into the traditional 5 GHz WLAN technology. The dual mode of operation primarily aims at offloading the 5 GHz cell of HiperLAN/2 in very dense urban deployments. Neighborhood discovery and route selection are the basic components of CANA, where the AP is responsible for allocating the resources and establishing the routes at both modes of operation. CANA introduces modifications to the MAC of HiperLAN/2 regarding new messages and framing considerations in oder to allow for the new routing functionalities. Besides, switching between different modes of operation has a large impact on the achievable performance of CANA.

Wireless Sensor Networks (WSNs)

Wireless Sensor Networks have revently emerged as a hot, new research area in the broad field of (wireless) computer networking. Research interest in WSNs has been stimulated by the very recent advances in the micro-electro-mechanical systems (MEMS) and the wireless communications technology, which have made it possible to produce low-cost, tiny-sized sensors with wireless networking capabilities. WSNs are expected to be ubiquitous in the future, with wide deployment both in the military and the commercial sectors.

Researchers envisage a large set of futuristic applications to be made possible with the aid of WSNs. In particular, they promise that WSNs will revolutionize the way humans interact with their physical surroundings. Some examples of such applications include military applications (e.g. battlefield surveillance, friendly / hostile forces tracking, monitoring of equipment), environmental monitoring (e.g. flood / forest fire detection, space exploration, biological attack detection), health applications (e.g. integrated patient monitoring, diagnostics, tracking and monitoring doctors and patients inside a hospital) and many other commercial applications (e.g. home / office smart environments, environmental control in buildings).

Wireless ad hoc Sensor Networks are a vastly unexplored area. The current focus of research is predominantly directed towards the following topics: