Energy efficient and adaptive service advertisement, discovery and provision for mobile ad hoc networks

Abstract

Mobile Ad Hoc Networks (MANETs) are networks of mobile computing nodes (e.g. portable computers, PDAs etc.) equipped with wireless interfaces and communicating with each other without relying on any infrastructure. In these networks each mobile node may act as a client, a server and a router. MANETs have emerged to fulfill the need for communication of mobile users in locations where deploying a network infrastructure is impossible, or too expensive, or simply is not available at that time. Characteristic scenarios for MANETs are disaster relief operations, battlefields and locations where infrastructure-based WLAN coverage (also called hotspots) is not provided and wireless WANs (e.g. GPRS/UMTS) are too expensive to use or too slow. Most of the research on MANETs has focused on issues dealing with the connectivity between mobile nodes in order to cope with the dynamism of such networks and the arising problems thereof. This dynamism is due to the mobility of nodes, the wireless channel’s adverse and fast changing conditions and the energy limitations of mobile nodes, all of which lead to frequent disconnections and/or node failures. These research efforts have led to the creation of a sound technical basis for dealing with the aforementioned problems regarding node connectivity in MANETs (mainly through routing protocols, link layer protocols etc.). However, solving the problems of connectivity alone is not sufficient for the adoption of MANETs. Since their basic role is to allow mobile users to exchange data and use each other’s services, there is also a need for architectures, mechanisms and protocols for Service Discovery and Provision. Service Discovery is defined in general as the process allowing networked entities to: i) advertise their services, ii) query about services provided by other entities, iii) select the most appropriate services and iv) invoke the services. Service Discovery has been mainly addressed in the context of wired networks in the past. In that context, clients and especially servers are typically powerful and resource-rich machines connected to the wired network. Service discovery and advertisement for wired networks generally follows a centralized or semi-centralized architecture assuming that well-known and “always on” service registries (or directories) exist for matching service requests to available services. Most of these architectures also rely on inefficient flooding techniques for service discovery and advertisement since resource scarcity is not a key issue. All the characteristics mentioned above, render those architectures inappropriate for service discovery in MANETs. In this context, the requirements are radically different than those of wired networks. In MANETs both clients and servers are more lightweight devices with limited resources. The assumption of (possibly dedicated and) always-available nodes serving as service directories is no longer valid. Also, frequent disconnections are a major issue affecting service availability. Disconnections may happen due to node mobility, due to depletion of the energy resources of the nodes, or even due to switching-off of some nodes. It is rather straightforward that in such environments it is of utmost importance to have energy efficient service discovery mechanisms. In this thesis we develop two energy efficient service discovery protocols integrated into the routing process in order to avoid redundant network messaging. Both developed protocols are distributed in nature and employ both proactive and reactive information dissemination techniques. The performance of the developed protocols is thoroughly investigated through extensive simulations in terms of energy consumption, service discoverability and achievable service availability under a wide range of settings (e.g. mobility, network density, channel characteristics, service replication, traffic patterns). The first (basic) protocol, called Extended Zone Routing Protocol (E-ZRP) is used in our study for comparing cross-layer with application-layer based service discovery protocols. Although integrating service and route discovery has been already proposed in the past, previous work regarding the energy gains of implementing service discovery at the routing layer as compared to implementing it at the application layer (as a separate process) is problematic due to the following reasons: i) most approaches either deal with energy only implicitly (by measuring the overhead in number of packets) or employ non-realistic energy consumption modeling, ii) the majority of proposed approaches involve performance analysis comparisons of the developed route and service discovery protocols against unrealistic application layer based service discovery protocols which are based on global flooding and hence are not suitable to MANETs, and iii) none of those approaches takes into consideration the impact of protocol message sizes on protocol performance. In our work we have performed full-stack simulations employing a realistic energy consumption model, accounting for the actual energy consumption of the nodes, in order to reveal the real gains from integrating the service discovery process with the routing process. The integrated service discovery protocol, named E-ZRP proves to be much more efficient compared to a similar but application layer based service discovery protocol. More importantly, we developed an even more sophisticated service discovery protocol, called Adaptive SerVicE and Route Discovery ProTocol for MANETs (AVERT). AVERT demonstrates superior efficiency than the best alternatives, mainly due to its built-in capability of adapting to a volatile environment such as a MANET. Using a monitoring mechanism for traffic seen locally, a node may adapt the operation of AVERT to best match the fluctuating traffic and mobility conditions typically found in MANETs. In parallel to the aforementioned research effort, we developed a novel mechanism for service providers to select to serve those clients from a MANET that can maximize their profits. Optimized service provisioning is a challenging problem in dynamic environments such as MANETs. We consider the nodes in MANETs to be independent, rational agents trying to maximize their profits through service provision. We model this problem as a Generalized Assignment Problem (GAP). We adopt a pay-as-you-go model, where clients pay for the service as long as they are receiving the service, since a pay-in-advance model would be unfair especially in MANETs where connection loss is very probable. We introduce into the proposed profit maximization algorithm expected payoffs based on estimates of server-to-client connectivity. Those estimations can be used for computing the actual payoff that will be received from any client that is selected by the service provider. We experimentally study cases with non-cooperative and cooperative servers and investigate the gain of the estimate based profit maximization algorithm versus a classic profit maximization algorithm, which does not take into account the network’s dynamics that affect server-to-client connectivity. We especially study the duration of connectivity (irrespectively of path changes) between two nodes of a MANET. Previous work, both analytical and experimental, has focused only on estimating the duration of a single path between a client and a server without considering changes to a path’s length caused by node mobility. The connectivity between two nodes irrespectively of changes in paths or the path length has not been investigated. In this dissertation we derive an approximation of the connectivity duration, taking into account the network’s density (number of nodes, terrain size, wireless transmission range), the node speed and the initial distance (in number of hops) between two nodes (one representing a client and the other a server). Simulations show that our approach achieves up to three-fold improved server profits compared to the classical one and is especially suited for MANETs with high-mobility and/or low density, which verifies that the proposed model accurately captures the effects of server to client connectivity on the overall performance. Summing up, in this thesis we propose energy efficient highly adaptive service discovery protocols integrated with hybrid routing protocols. We implemented and experimentally evaluated those protocols to show their energy and service discoverability/availability gains under different MANET conditions and against similar application layer-based as well as routing layer-based protocols. We also developed and evaluated an innovative mechanism for allowing mobile service providers to maximize their profits when offering their service in MANETs, by estimating their connectivity to candidate clients.