In wireless ad hoc networks, the resources such as bandwidth, power, computing ability, etc., for end users are limited by the environments and hardware. In addition, the mobility of each user is different. Furthermore, the varied wireless networks with different properties such as transmission rate, coverage, power and protocols make it rarely difficult to establish and maintain the communications through the multiple intermediate nodes which are mobile devices. This dissertation will focus on the following three issues: 1. Most homogeneous wireless networks only considering one or less resources of the mobile device can not select and distribute the routes. In addition, it can cause the load of the intermediate nodes to increase. 2. The various wireless networks have different characteristics of resources. The route selection and distribution algorithms proposed before in homogeneous wireless networks are not adapted for the heterogeneous wireless networks. 3. Most route selection and distribution algorithms are designed for specific type of wireless environments (such as only for proactive type or reactive type). For different environment and different mobility, its cost will be different. To allow an environment-aware based adaptive management for heterogeneous wireless networks with different characteristics of resources becomes an important issue. In homogeneous wireless ad hoc networks, the resources of the mobile devices such as bandwidth, power, computing ability, etc., are limited and different by the environments and hardware. To evaluate the individual resource of each mobile device, the route distribution and selection algorithm considering the multiple resource variations in wireless ad hoc networks is proposed. First, the evaluation and management for individual resource of each mobile device such as bandwidth, power, and computing ability, are proposed. Second, according to the proposed algorithm, a mobile device can be estimated whether it supports the QoS or not. In addition, these resources evaluation results are transformed as the bottleneck resource information. At last, according to the bottleneck resource information of all the found routes, the route distributed through different intermediate nodes with most resources is selected for load distribution and balance. Considering the wireless network infrastructure today including 3G wireless communication, IEEE 802.11 wireless local area network, and wireless ad hoc networks, the characteristics such as transmission rates, bandwidth, power consumption, and transmission range of these wireless structures are not the same. In other words, the routing selection algorithm for homogeneous wireless networks may not be flexible for another wireless network. In this thesis, these different wireless network structures are integrated into one heterogeneous wireless network. Individual characteristics such as transmission rates, bandwidth, power consumption, and transmission range of these wireless structures are evaluated. According to the adaptive resource evaluation and route selection algorithm for the heterogeneous wireless networks, the route with the lowest cost and most resources is selected based on the integrated information of each resource estimation and the bottleneck information of each route found. Besides considering the characteristic of the heterogeneous wireless networks, the module (type) of the route selection and distribution algorithms also induces different costs and performance. The existing algorithms can be defined and divided into two typical types: proactive (table-driven) protocol and reactive (source initiated) protocol. The proactive type protocol pays the memory and periodical update (bandwidth consumption) costs for selecting the routing directly. In opposite, the reactive type protocol saves the costs but may increase the overhead for finding a routing path to the destination. To decrease the total costs of finding and maintaining routing paths, the environment-aware based adaptive management for heterogeneous wireless networks is proposed in this thesis. Corresponding to the movement of the users, the appropriate type of the routing algorithm should be selected for reducing the total costs of finding routing paths. In the adaptive management, we propose the type selection process to individually evaluate the cost of the two type protocols (proactive and reactive) via considering the protocols and the mobility of the users. According to the evaluation results, the appropriate protocol with less cost will be selected for finding and maintaining the routes in the heterogeneous wireless networks. According to the simulation, the routing selection and distribution algorithm proposed in this dissertation can not only effectively distribute the routing paths but also balance the load within homogeneous or heterogeneous wireless networks. Corresponding to the mobility of the users, the suitable type of routing protocol can be selected. Furthermore, the cost for routing paths searching, selection and maintenance is decreased. The block rate of these routing paths is reduced. Overall, according to the simulation, this dissertation makes the major contributions as follows: 1. The individual resource evaluations and managements for the mobile devices in the homogeneous wireless networks are proposed. The routes which satisfy the QoS can be selected and distributed according to the proposed algorithm. 2. The various wireless networks with different are integrated into a heterogeneous wireless network. The route search, selection, and maintenance algorithm for the hybrid properties heterogeneous wireless networks is proposed. 3. The classification to separate and classify the route search and selection algorithms is proposed. Corresponding to the mobility of the users, the environment-aware based adaptive management for heterogeneous wireless networks is proposed to reduce the costs caused by route search, selection, and maintenance.

Le passage à l’échelle des protocoles de routage est un des problèmes les plus critiques pour les réseauxmobiles sans fil à grande envergure. Dans ce cadre, le concept de clusterisation peut être mis à profit dans lafonction de routage afin d’améliorer les performances de ces réseaux. En premier lieu, cette thèse présentenotre algorithme de clusterisation à 1-saut alpha-SSCA (α-Stability Structure Clustering Algorithm) qui apour objectif d’améliorer la stabilité de la structure des clusters. Un algorithme générique de clusterisationà K-sauts est également proposé en ayant le même but de stabilité visé par alpha-SSCA tout en réduisant lenombre de clusters générés et en étant indépendant de la métrique d’élection des cluster-heads. Ensuite, nousprésentons notre proposition d’un protocole de routage à état des liens des clusters qui exploite les apports denotre mécanisme de clusterisation α-SSCA. Ce protocole, appelé CLSR (Cluster-based Link State Routing),vise à réduire le trafic de contrôle afin d’améliorer les performances du réseau à large échelle. Nous avonsproposé aussi une version hiérarchique du protocole CLSR. Ce protocole de routage introduit une hiérarchiedans la structure des clusters qui permet de réduire le nombre de clusters en groupement des clusters prochesdans un même cluster. L’objectif principal de ce protocole hiérarchique est d’améliorer la scalabilité de CLSRquand le nombre de noeuds dans le réseau augmente considérablement. / Scalability is one of critical challenges for routing protocols in large scale mobile wireless networks. In thiscontext, clustering technique seems a promising approach to overcome the scalability problem. First, we proposea one hop clustering algorithm, alpha-SSCA (alpha-Stability Structure Clustering Algorithm), whichaims to improve the stability of the clusters structure. Second, we present a proposal of a generic K-hopsclustering algorithm which is independent of the metrics used to elect cluster-heads. The main contributionof this last algorithm is to enhance the stability of the clusters structure while reducing the number of clusters.Clustering mechanism is introduced in our proposed routing protocol CLSR (Cluster-based Link StateRouting) in order to reduce the control overhead. The main objective of CLSR is to take profit of the stablestructure of clusters to enhance the network scalability.We propose also a second proactive link-state protocolwhich is based on hierarchical clustering. This protocol makes use of hierarchical clustering to more reducethe routing overhead.

abstract: The primary function of the medium access control (MAC) protocol is managing access to a shared communication channel. From the viewpoint of transmitters, the MAC protocol determines each transmitter's persistence, the fraction of time it is permitted to spend transmitting. Schedule-based schemes implement stable persistences, achieving low variation in delay and throughput, and sometimes bounding maximum delay. However, they adapt slowly, if at all, to changes in the network. Contention-based schemes are agile, adapting quickly to changes in perceived contention, but suffer from short-term unfairness, large variations in packet delay, and poor performance at high load. The perfect MAC protocol, it seems, embodies the strengths of both contention- and schedule-based approaches while avoiding their weaknesses. This thesis culminates in the design of a Variable-Weight and Adaptive Topology Transparent (VWATT) MAC protocol. The design of VWATT first required answers for two questions: (1) If a node is equipped with schedules of different weights, which weight should it employ? (2) How is the node to compute the desired weight in a network lacking centralized control? The first question is answered by the Topology- and Load-Aware (TLA) allocation which defines target persistences that conform to both network topology and traffic load. Simulations show the TLA allocation to outperform IEEE 802.11, improving on the expectation and variation of delay, throughput, and drop rate. The second question is answered in the design of an Adaptive Topology- and Load-Aware Scheduled (ATLAS) MAC that computes the TLA allocation in a decentralized and adaptive manner. Simulation results show that ATLAS converges quickly on the TLA allocation, supporting highly dynamic networks. With these questions answered, a construction based on transversal designs is given for a variable-weight topology transparent schedule that allows nodes to dynamically and independently select weights to accommodate local topology and traffic load. The schedule maintains a guarantee on maximum delay when the maximum neighbourhood size is not too large. The schedule is integrated with the distributed computation of ATLAS to create VWATT. Simulations indicate that VWATT offers the stable performance characteristics of a scheduled MAC while adapting quickly to changes in topology and traffic load. / Dissertation/Thesis / Ph.D. Computer Science 2013

Mobile wireless environments present new challenges to the design and validation of system supports for facilitating development of mobile applications. This dissertation concerns two major system-support mechanisms in mobile wireless networks, namely, location management and service management. We address this research issue by considering three topics: location management, service management, and integrated location and service management. A location management scheme must effectively and efficiently handle both user location-update and location-search operations. We first quantitatively analyze a class of location management algorithms and identify conditions under which one algorithm may perform better than others. From insight gained from the quantitative analysis, we design and analyze a hybrid replication with forwarding algorithm that outperforms individual algorithms and show that such a hybrid algorithm can be uniformly applied to mobile users with distinct call and mobility characteristics to simplify the system design without sacrificing performance. For service management, we explore the notion of location-aware personal proxies that cooperate with the underlying location management system with the goal to minimize the network communication cost caused by service management operations. We show that for cellular wireless networks that provide packet services, when given a set of model parameters characterizing the network and workload conditions, there exists an optimal proxy service area size such that the overall network communication cost for service operations is minimized. These proxy-based mobile service management schemes are shown to outperform non-proxy-based schemes over a wide range of identified conditions. We investigate a class of integrated location and service management schemes by which service proxies are tightly integrated with location databases to further reduce the overall network signaling and communication cost. We show analytically and by simulation that when given a user's mobility and service characteristics, there exists an optimal integrated location and service management scheme that would minimize the overall network communication cost for servicing location and service operations. We demonstrate that the best integrated location and service scheme identified always performs better than the best decoupled scheme that considers location and service managements separately. / Ph. D.

Un réseau sans fil mobile est une collection de noeuds mobiles connectés via des liens sans fil. Le noeud mobile peut être une personne portant un terminal mobile, un animal avec une étiquette électronique, un véhicule ou tout autre appareil mobile doté de capacités de communication sans fil. Cette thèse traite deux importants problèmes dans les réseaux sans fil mobiles : la localisation et la détection des conflits. La localisation est l’estimation des positions absolues ou relatives des noeuds mobiles. La détection des conflits est la prédiction des potentiels futurs conflits entre les noeuds mobiles. Un conflit est une situation dans laquelle deux ou plusieurs noeuds mobiles se trouvent à une distance inférieure à une distance minimale requise. La détection des conflits est particulièrement nécessaire dans les réseaux mobiles où les noeuds risquent de trop se rapprocher les uns des autres et se heurter.La première contribution de cette thèse est un nouvel algorithme de localisation pour les réseaux sans fil mobiles. L’algorithme proposé est distribué et nécessite un faible coût de calcul et de communication permettant son utilisation par des noeuds à ressources limitées. En particulier, un petit ensemble de noeuds avec des positions connues, appelés des nœuds ancres, diffusent périodiquement leurs coordonnées. Chaque noeud mobile avec une position inconnue collecte les coordonnées des noeuds ancres, les attribue des poids en fonction de différentes métriques (par exemple, la qualité de la liaison sans fil, le temps de réception) et enfin estime sa position en tant que la moyenne pondérée de toutes les coordonnées collectées. La deuxième contribution de cette thèse consiste en un algorithme de détection de conflit nommé SLIDE. SLIDE est distribué et à faible complexité: chaque noeuds mobile utilise des simples inégalités mathématiques afin de prédire avec précision et en temps opportun les futurs conflits avec les noeuds voisins. En outre, SLIDE abandonne l’hypothèse restrictive des positions et vitesses précises ainsi que des communications non perturbées afin de garantir son efficacité dans les applications du monde réel. La troisième et dernière contribution de cette thèse est un modèle stochastique qui évalue les risques des conflits dans un réseau sans fil mobile où les noeuds mobiles se déplacent dans le même espace partagé. Contrairement à la plupart des modèles stochastiques existants, le modèle proposé est simple, générique et ne nécessite que deux paramètres d’entrée: le nombre de noeuds mobiles et le paramètre λ caractérisant le temps d’inter-contact entre une paire de noeuds mobiles. Le paramètre λ peut être difficile à estimer expérimentalement. Nous proposons donc une expression générique pour λ et puis nous la spécifions pour deux modèles de mobilité couramment utilisés. Toutes les contributions de cette thèse sont validées en utilisant des simulations basées sur le simulateur d’événements discrets OMNeT ++. / A mobile wireless network is a collection of mobile nodes connected via wireless links. The mobile node can be a person carrying a mobile terminal, an animal with an embedded sensor (electronic tag), a vehicle or any other mobile device with wireless communication capabilities. This thesis deals with two fundamental issues in mobile wireless networks: localization and conflict detection. Localization is the estimation of the absolute or relative positions of the mobile nodes. Conflict detection is the prediction of potential future conflicts between the mobile nodes. A conflict is a situation in which two or more mobile nodes are within an unsafe distance from one another. Conflict detection is a crucial requirement for mobile networks where the nodes can get too close to each other and collide.The first contribution of this thesis is a new weighted localization algorithm for mobile wireless networks. The proposed algorithm is distributed and requires low computational and communication overheads enabling its use in resource-limited nodes. In particular, a small set of nodes with known positions, called beacon nodes, are periodically broadcasting their coordinates. A mobile node with an unknown position collects the beacon nodes coordinates, attributes them weights based on different metrics (e.g, link quality, reception time) and finally estimates its position as the weighted average of all the collected coordinates. The second contribution of this thesis consists in a straight line conflict detection algorithm called SLIDE. SLIDE is distributed and lightweight: each mobile node uses simple mathematical inequalities in order to accurately and timely predict future conflicts with the surrounding nodes. Furthermore, SLIDE drops the restrictive assumption of perfect sensing capabilities and perturbation-free environment in order to guarantee its efficiency in real world applications. The third and last contribution of this thesis is a stochastic model that assesses the conflicts risks in a mobile wireless network where the mobile nodes are moving in the same shared space. Unlike most of the existing stochastic models, the proposed model is simple, generic and requires only two input parameters: the number of mobile nodes and the parameter λ characterizing the inter-contact time between a pair of mobile nodes. The parameter λ may be difficult to estimate experimentally. We therefore provide a generic explicit expression for λ and then specify this generic expression for two commonly used mobility models. All the contributions of this thesis are validated through extensive simulations based on the discrete-event simulator OMNeT++.

In this thesis we study several resource management problems in two classes of wireless networks. The thesis is in two parts, the first being concerned with game theoretic approaches for cellular networks, and the second with control theoretic approaches for mobile opportunistic networks. In Part I of the thesis, we first investigate optimal association and power control for the uplink of multichannel multicell cellular networks, in which each channel is used by exactly one base station (BS) (i.e., cell). Users have minimum signal to interference ratio(SINR) requirements and associate with BSs where least transmission powers are required. We formulate the problem as a non-cooperative game among users. We propose a distributed association and power update algorithm, and show its convergence to a Nash equilibrium of the game. We consider network models with discrete mobiles(yielding an atomic congestion game),as well as a continuum of mobiles(yielding a population game). We find that the equilibria need not be Pareto efficient, nor need they be system optimal. To address the lack of system optimality, we propose pricing mechanisms. We show that these prices weakly enforce system optimality in general, and strongly enforce it in special settings. We also show that these mechanisms can be implemented in distributed fashions. Next, we consider the hierarchical problems of user association and BS placement, where BSs may belong to the same(or, cooperating) or to competing service providers. Users transmit with constant power, and associate with base stations that yield better SINRs. We formulate the association problem as a game among users; it determines the cell corresponding to each BS. Some intriguing observations we report are:(i)displacing a BS a little in one direction may result in a displacement of the boundary of the corresponding cell to the opposite direction;(ii)A cell corresponding to a BS may be the union of disconnected sub-cells. We then study the problem of the placement of BSs so as to maximize service providers’ revenues. The service providers need to take into account the mobiles’ behavior that will be induced by the placement decisions. We consider the cases of single frequency band and disjoint frequency bands of operation. We also consider the networks in which BSs employ successive interference cancellation(SIC) decoding. We observe that the BS locations are closer to each other in the competitive case than in the cooperative case, in all scenarios considered. Finally, we study cooperation among cellular service providers. We consider networks in which communications involving different BSs do not interfere. If service providers jointly deploy and pool their resources, such as spectrum and BSs, and agree to serve each others’ customers, their aggregate payoff substantially increases. The potential of such cooperation can, however ,be realized only if the service providers intelligently determine who they would cooperate with, how they would deploy and share their resources, and how they would share the aggregate payoff. We first assume that the service providers can arbitrarily share the aggregate payoff. A rational basis for payoff sharing is imperative for the stability of the coalitions. We study cooperation using the theory of transferable payoff coalitional games. We show that the optimum cooperation strategy, which involves the acquisition of channels, and deployment and allocation of BSs to customers, is the solution of a concave or an integer optimization problem. We then show that the grand coalition is stable, i.e., if all the service providers cooperate, there is an operating point offering each service provider a share that eliminates the possibility of a subset of service providers splitting from the grand coalition; this operating point also maximizes the service providers’ aggregate payoff. These stabilizing payoff shares are computed by solving the dual of the above optimization problem. Moreover, the optimal cooperation strategy and the stabilizing payoff shares can be obtained in polynomial time using distributed computations and limited exchange of confidential information among the service providers. We then extend the analysis to the scenario where service providers may not be able to share their payoffs. We now model cooperation as a nontransferable payoff coalitional game. We again show that there exists a cooperation strategy that leaves no incentive for any subset of service providers to split from the grand coalition. To compute this cooperation strategy and the corresponding payoffs, we relate this game and its core to an exchange market and its equilibrium. Finally, we extend the formulations and the results to the case when customers are also decision makers in coalition formation. In Part II of this thesis, we consider the problem of optimal message forwarding in mobile opportunistic wireless networks. A message originates at a node(source), and has to be delivered to another node (destination). In the network, there are several other nodes that can assist in relaying the message at the expense of additional transmission energies. We study the trade-off between delivery delay and energy consumption. First, we consider mobile opportunistic networks employing two-hop relaying. Because of the intermittent connectivity, the source may not have perfect knowledge of the delivery status at every instant. We formulate the problem as a stochastic control problem with partial information, and study structural properties of the optimal policy. We also propose a simple suboptimal policy. We then compare the performance of the suboptimal policy against that of the optimal control with perfect information. These are bounds on the performance of the proposed policy with partial information. We also discuss a few other related open loop policies. Finally, we investigate the case where a message has to be delivered to several destinations, but we are concerned with delay until a certain fraction of them receive the message. The network employs epidemic relaying. We first assume that, at every instant, all the nodes know the number of relays carrying the packet and the number of destinations that have received the packet. We formulate the problem as a controlled continuous time Markov chain, and derive the optimal forwarding policy. As observed earlier, the intermittent connectivity in the network implies that the nodes may not have the required perfect knowledge of the system state. To address this issue, we then obtain an ODE(i.e., a deterministic fluid) approximation for the optimally controlled Markov chain. This fluid approximation also yields an asymptotically optimal deterministic policy. We evaluate the performance of this policy over finite networks, and demonstrate that this policy performs close to the optimal closed loop policy. We also briefly discuss the case where message forwarding is accomplished via two-hop relaying.