Clustering Coefficient CCDF Complementary Cumulative Density Function CDR Call Detail

In public warning message systems, information dissemination across the network is a critical aspect that has to be addressed. Dissemination of warning messages should be such that it reaches as many nodes in the network in a short time. In communication networks those based on device to device interactions, dissemination of the information has lately picked up lot of interest and the need for self organization of the network has been brought up. Self organization leads to local behaviors and interactions that have global effects and helps in addressing scaling issues. The use of self organized features allows autonomous behavior with low memory usage. Some examples of self organization phenomenon that are observed in nature are Lateral Inhibition and Flocking. In order to provide self

List of Tables

Achieving small world properties is an attractive way to enhance information dissemination across the network. In small world model rewiring of links in the network is performed by altering the length and the direction of the existing links. In an autonomous wireless environment such organization can be achieved using self organized phenomenon like Lateral inhibition and Flocking and beamforming (a concept in communication).

Towards this, we first use Lateral Inhibition, analogy to Flocking behavior and beamforming to show how dissemination of information can be enhanced. Lateral Inhibition is used to create virtual regions in the network. Then using the analogy of Flocking rules, beam properties of the nodes in the regions are set. We then prove that small world properties are achieved using average path length metric. However, the proposed algorithm is applicable to static networks and Flocking and Lateral Inhibition concepts, if used in a mobile scenario, will be highly complex in terms of computation and memory.

In a mobile scenario such as human mobility aided networks, the network structure changes frequently. In such conditions dissemination of information is highly impacted as new connections are made and old ones are broken. We thus use stability concept in mobile networks with beamforming to show how information dissemination process can be enhanced. In the algorithm, we first predict the stability of a node in the mobile network using locally available information and then uses it to identify beamforming nodes. In the algorithm, the low stability nodes are allowed to beamform towards the nodes with high stability. The difference between high and low stability nodes is based xix xx on threshold value. The algorithm is developed such that it does not require any global knowledge about the network and works using only local information. The results are validated using how quickly more number of nodes receive the information and different state of the art algorithms. We also show the effect of various parameters such as number of sources, number of packets, mobility parameters and antenna parameters etc. on the information dissemination process in the network.

In realistic scenarios however, the dynamicity in the network is not only related to mobility.

Dynamic conditions also arise due to change in density of nodes at a given time. To address effect of such scenario on the dissemination of information related to public safety in a metapopulation, we use the concepts of epidemic model, beamforming and the countrywide mobility pattern extracted from the D4D dataset. Here, we also propose the addition of three latent states to the existing epidemic model (SIR model). We study the transient states towards the evolution of the number of devices having the information and the difference in the number of devices having the information when compared with different cases to evaluate the results. Through the results we show that enhancements in the dissemination process can be achieved in the addressed scenario.

Acknowledgement

First, I would like to thank Prof. Monique Becker for her constant support and guidance during my research without which this thesis would have not been possible. I would like to also thank her for her patient updates and significant feedbacks to my numerous drafts and her hospitality to my numerous visits to her place in south and east. I would also like to thank her for her errands to University of Pierre and Marie Curie during my initial few month of the research. Post lunch interactions with her certainly helped me build on my research both conceptually and methodically.

It was indeed my great fortune to carry out my PhD studies under her esteemed guidance. I would then like to thank Dr. Vincent Gauthier, my supervisor, especially for his extensive help and friendly nature. His intrinsic detailing and thought process resulted in profound improvements in my research. His constant updates on the latest research helped me broaden my state of the art in my field of research. I would also like to thank him for his efforts towards making it possible for me to attend summer school at NECSI, MIT. Being a beginner in French, I would like to thank him for being occasional translator to me and his kindness for driving me to the University of Pierre and Marie Curie and helping me out with the contract signing. I am also grateful to Prof. André-Luc Beylot, Prof. Xavier Lagrange, Prof. Marcelo Dias De Amorim, Dr. Philippe Jacquet, Dr. Frederica Darema and Prof. Nazim Agoulmine for being members of my thesis evaluation committee and providing their valuable comments on my thesis work.

I would like to thank Prof. Chai Kiat Yeo and Prof. Bu Sung Lee to providing me an opportunity to work with them during my initial months of my research. I thank Dr. Abhik Banerjee with whom I worked closely during my first year of research and for helping me with research methodologies. At Telecom SudParis, I would like to specially thank Valerie Mateus and Françoise Abad for helping me with my numerous missions especially to US and with the administrative works. Nevertheless, I would like to thank other people at Telecom SudParis especially in "Réseaux et Services de Télécommunications" department for helping me during my thesis. These people include, Prof.

Michel Marot, Prof Hossam Afifi, Dr. Charbel Nicolas and Dr. Mohammed Haykel Zayani. However, I am also thankful to other members of "Réseaux et Services de Télécommunications" department with whom I had many technical interactions. I want to express special thanks to Dr. Ashish Gupta, Dr. Manoj Panda, Dr. Arshad Ali and xxi

Introduction

Due to the recent advancements in the technology and human needs, deployment of wireless networks in recent times has picked up a lot of attention. Many properties that affect the performance of wireless networks have been identified [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF]. Further, many studies have been focused on how to address the scaling issues, constant supervision and technological development. Vast topological perils in the deployment of wireless networks have made it very hard for humans to constantly monitor the needs of the wireless systems in-terms of energy and technological advancements [START_REF] Dressler | A survey on Bio-Inspired Networking[END_REF]. Not only the above mentioned limitations require great consideration but many other factors such as networking constraints, environment interactions, resource utilization, development of different types of heterogeneous network architectures also require great attention [START_REF] Dressler | A survey on Bio-Inspired Networking[END_REF]. The evolution of wireless ad hoc network makes it tough for existing algorithms to answer many intrinsic details associated with it such as, increased contention and collision. This leads to a great need for the algorithms that should perform well in "self*" environment 1 . The growth of networks has made the researchers to look into complex, distributed and adaptive systems that could answer most of these questions and scale with the network. Thus, in this dissertation, we build the algorithms such that self organized features are provided to the network in order to achieve faster dissemination.

For a system to be considered adaptive, it should follow four paradigms [START_REF] Prehofer | Self-Organization in Communication Networks: Principles and Design Paradigms[END_REF]. The paradigms state that the entities in the system should operate in an autonomous manner using locally available information, implicitly coordinate, have short lived memory and should adapt to the changes in the environment. To achieve global performance characteristics using only local information in a distributed scenario is a hard task. Consider Nature, it very efficiently solves most of the complex problems using very simple rules and by following these four paradigms. The application of the Natural phenomenon in computing dates back to the times of Sir Allan Turing when he modeled the patterns on the animal skin using simple rules. His research widely opened a field for researchers to investigate the use of naturally occurring phenomenon in their respective research areas.

Challenges

In Wireless Networks, despite the use of the local information in an autonomous environment and above mentioned deployment issues, efficient transmission of information from one node to another is still the most important issue. In a realistic environment, in wireless networks, transmission of information is affected by many factors like non uniform deployment, dynamic topology, lack of centralized infrastructure and limited resources. Moreover, in different types of wireless networks, several different associated properties affect the dissemination process. For example, in mobile wireless networks especially Pocket Switched Networks and Device to Device communication network, the characteristics of human behavior and human mobility patterns affect the dissemination of information.

Consider a public warning message that has to be disseminated across the population. In static wireless network, a network that does not change in a given time duration, the non-uniform deployment of nodes could lead to several disconnected network components. Information flow between two components will not be possible until a connection is established between the two components.

This limits the dissemination process to a certain fraction of the population. In a scenario dealing with public warning message, a fraction of population only having the information is not sufficient.

Full population should be able to receive the message.

Consider a static network where nodes do not move and lack mobility characteristics. Now consider that, at some instant, perturbation has occurred in the network causing changes in the network topology. Some factors that cause the network topology to change are: a bridge node within a component being removed from the component due to energy limitations causing the component to break into several smaller components and occurrence of a natural disaster, for example, landslides and earthquakes. In such a case, a strongly connected network component could break into several small components. Here we call the new formed network as a static network because the network will not change unless the above factors again occur. In such disaster hit scenarios, quick dissemination of public warning message plays an important role. The quicker relief reaches, the better it is.

However, due to changes in the network topology where the network broke into several components, the dissemination process is highly impacted as stated in the previous paragraph.

When the nodes in wireless network are mobile (Mobile ad hoc Network, Pocket Switched Networks, Delay Tolerant Networks, Device to device communication network), the topology of the underlying network changes frequently causing changes in the dissemination process. The mobility patterns of such networks is closely related to mobility patterns of human as devices are carried by humans. In low density scenarios, mobility pattern may leave the network disconnected and hamper the dissemination process. However, studies argue that information dissemination is enhanced through mobility. In a metapopulation (where the population is spatially divided into communities and the interact at some level), mobility has been proved to enhance the information dissemination process. However, in a scenario where a public warning message has to be disseminated quickly in the entire network, a challenging task is to formulate an efficient and effective algorithm that achieves the goal as soon as possible.

In the growing needs of frequent changes in the technology, the network is highly dynamic. In real scenarios dynamic population causes network wide changes thereby affecting the dissemination process. When the network is mobile, the information dissemination is also affected by the region characteristics like the density and the distribution of the population in the region.

The above challenges motivate us to study how the information dissemination process can be enhanced in the network where nodes lack global knowledge about the network and are constrained by local one hop information. If the network is static and disconnected, how properties of a node can be used to disseminate the information from one component to another and if the network is mobile how dissemination process can be further enhanced. Towards this, in the next section we provide more details on the motivation of the research and our contributions.

Motivation and Contributions

In an ever-changing environment of wireless networks, it is important for the researchers to design and analyze algorithms using local information that can minimize overheads and guarantee performance for wireless network operations. In a wireless network where nodes have limited energy and limited memory the use of local information helps in lesser consumption of energy and memory. The interaction of nodes with their environment also plays a very important role in defining the node properties for efficient data transfer and information dissemination. Watts-Strogatz model [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF] is one well established model where by rewiring few links in the network, the average path length of the network is reduced while the network structure is maintained. The reduction in the average path length of the network directly relates to the faster dissemination of the information in the network as the overall diameter of the network is reduced. In wireless networks, however, rewiring can be achieved through M IM O technology by the adaptation of the transmission range and reception range. The adaptation of the transmission and reception range can be done using beamforming.

Beamforming is a technique where radiation from antenna elements that are embedded in wireless nodes interfere constructively and destructively. The interference gives rise to a long directional beam. Adaptation of transmission range and reception range being one clear direction, a key aspect of this work is based on how nodes can self organize their beams to facilitate the information dissemination process. On the whole, in this research, we are focused on how performance enhancements can be achieved in wireless networks in terms of faster information dissemination in the network in an optimal way with nodes incurring minimal overheads.

Towards this, our objective in Chapter 3 is to propose how local information and natural phenomenon like Flocking and Lateral Inhibition can be used effectively to gain performance in terms of faster information dissemination with low message overheads in a static network. In this Chapter, we focus on the non-uniform deployment of the static nodes working autonomously in a network comprising of several components. The autonomous behavior leads us to propose a decentralized approach where the nodes in the network communicate directly with each other as in device to device communication. In order to achieve connection between the components for the transmission of the information we use beamforming. However, the use of beamforming in the wireless ad hoc networks introduces asymmetries and can reduce the neighborhood size of the node. If all nodes beamform, the network will be highly asymmetrical and will lose its structure. These factors lead us to limit the number of nodes that beamform. The determination of the beamforming nodes and the beam properties thus is a key part of Chapter 3. The determination of the beamforming nodes and the nodes towards which the beams are to be directed is achieved through the analogy of Flocking and Lateral Inhibition. Analogous to the three Flocking rules, Alignment, Separation and Cohesion, in the algorithm design, we relate Alignment to the decision of the node to whether to beamform or not to beamform. We relate separation to no two neighbors beamforming in the same direction while we relate cohesion to setting the direction of the beam in the direction of the most central node.

Further, as the size of network increases, memory usage also increases. In order to limit the memory usage, a component in the network can be further logically subdivided (not changing the component structure). This division can be achieved through Lateral Inhibition. The use of Lateral Inhibition creates logical regions in the component. This also help us in limiting the number of nodes that beamform. The beams are directed toward the centroid of a region. The centroid of the region is determined using averaging technique. Through the results obtained it is noted that the algorithm not only enhances network performance in terms of low average path length and maintaining the clustering coefficient but also increases the connectivity.

However, in mobile wireless network, the above algorithm technique incurs lot of overhead due to constant changes in the network topology. Motivated by the properties of Pocket Switched Networks, in Chapter 4, we propose how the concept of stability and beamforming can be used in order to achieve faster information dissemination. In Pocket Switched Network, the properties of the network are closely dependent on the human mobility patterns, the network topology changes at every instant and device to device communication occurs. Recently, it is found that the jump length distribution of human mobility fits truncated power law distribution [START_REF] González | Understanding Individual Human Mobility Patterns[END_REF]. Mobility in the system can cause the network to break into several components thereby hampering the information dissemination process. However, mobility can also enhance the dissemination process as it can enforce new connections within the network [START_REF] Kivelä | Multiscale Analysis of Spreading in a Large Communication Network[END_REF]. Using the properties of human mobility, in Chapter 4 we propose how, at each instant, stability of a node can be computed using local information and how the stability measure can be used towards enhancing information dissemination.

In this Chapter we define the stability measure for a node as the fraction of connections kept intact by the node. We use the stability measure to determine whether the nodes should beamform or not and towards which nodes the beams should be directed.

However, in real scenarios, some researchers argue that truncated power law nature of human mobility is an estimate due to the sampling of the data [START_REF] Mossa | Truncation of Power Law Behavior in Scale-Free Network Models due to Information Filtering[END_REF] and depends on the region where the samples are collected. In [START_REF] González | Understanding Individual Human Mobility Patterns[END_REF] the mobility data used are the samples collected from United States.

While in much recent work [START_REF] Csáji | Exploring the Mobility of Mobile Phone Users[END_REF] the samples are collected from Portugal. Csáji et al. in [START_REF] Csáji | Exploring the Mobility of Mobile Phone Users[END_REF] found that the jump length distribution of human mobility has a cut off distance equal to 106 ± 10km and the power law exponent equal to 1.37 ± 0.06. Differences in the mobility pattern for a region, lead us to acquire D4D (Data for Development) dataset [START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF] created by Orange Labs. The dataset featured Call Detail Records (CDR) and mobility patterns for the users of Orange network service in the country of Ivory Coast.

In a spatial distribution of large population where community structure is evident and interactions are based on the movements and proximity interactions, dissemination in such metapopulation has been well studied [START_REF] Arino | Disease Spread in Metapopulation[END_REF][START_REF] Watts | Multiscale, Resurgent Epidemics in a Hierarchical Metapopulation Model[END_REF] using epidemic models. As the traditional dissemination algorithms, in the two Chapters 3 and 4 of this dissertation we also considered fixed density of nodes over time.

However, in real mobile device to device wireless communication scenario, variations in the density of the nodes has been overlooked. Thus, in Chapter 5, we propose how dynamic density affects the dissemination process and how beamforming and mobility can be used to enhance the dissemination process. Dynamic density can be achieved using sleep and wake of the mobile devices. In this Chapter we propose an update to a classical dissemination model (epidemic model), SIR model, with three additional states, E S , E I and E R , in order to incorporate dynamic node density. We associate each state in the SIR model to an additional state. We calls these additional states as the latent states (sleeping states). The nodes in the latent state do not participate in dissemination process. However, once a node becomes active (awake state), it again participates in the dissemination process. The transitions between the three active states (S, I, R) and the latent states and vice versa occurs with a defined rate.

Dissertation Organization

This dissertation is organized into two parts. The first part is dedicated to the algorithms developed with related work while the second part contains a set of appendices dealing with the analysis of the data obtained for the D4D challenge and similar work performed by us using flows in the network.

Part one is further divided such that it first provides an overview of the concepts used, like small world, beamforming, centrality, Flocking, Lateral Inhibition, human mobility, stability measure and epidemic models to name a few, in the dissertation with state of the art pertaining to the concepts in Chapter 2. The three main contributions then form the three Chapters of the dissertation, Chapter 3, Chapter 4 and Chapter 5 respectively. Chapter 3 outlines the algorithm for the static network, Chapter 4 proposes to use stability measure and beamforming while Chapter 5 incorporates dynamic density scenario for achieving enhanced information dissemination. All Chapters contain a discussion on state of the art pertaining to the proposed idea, algorithm, simulation results and conclusion. The Chapters are then followed by a comprehensive conclusion and future perspectives.

Part two consists of a parallel work performed by us that relates to how small world properties in wireless networks can be achieved using flows in the network, the analysis of one of the dataset received from Orange Labs towards the D4D challenge, publications during the course of the thesis and an extensive bibliography.

CHAPTER2

State of the Art and Useful Concepts

In this Chapter, we discuss the concepts that are used for achieving the goals of this dissertation and discuss the state of the art related to those concepts. We first present the concepts like Self Organization (Section 2.1), Small World (Section 2.2), Centrality measures (Section 2.2.1), Beamforming (Section 2.3), Lateral Inhibition (Section 2.4), Flocking (Section 2.5) and Non-uniform Node Deployment (Section 2.6) to provide an understanding for Chapter 3. We then provide an overview of Human Mobility (Section2.7), Stability Measures (Section 2.8) and Information Dissemination (Section 2.9) which form the basis for Chapters 4 and 5.

Self Organization

In the 1940's, Asby [START_REF] Ashby | Principles of the Self-Organizing Dynamic System[END_REF], in his work on cybernetics provided the notion and definition of self organization. According to him, self organization is the expression of global behavior in terms of cooperation among individual entities through simple means without any controlling agent.

In general, cooperation leads to different emergent behaviors such as grouping and synchronization in the system and achieves scalability due to the absence of a central controlling agent. This evolution of behavior also leads to changes and diversities in the system and vice versa. Evolution has been very well explored in the context of biology. Over the years, the focus of the researchers has remained towards the study of evolution over time and scale. An example of evolution over scale, also called emergence [START_REF] Sayama | Complex System Organization Map[END_REF], is the change that occurs in the system due to the interaction of multiple subsystems. This means that the collective effort leads to the evolution of the system that has completely different properties from its subsystems. Some examples of collective effort over scale observed in biology are (i) different organs in a human body interact with each other to give an 9 individual that has different characteristics than the organs, (ii) fireflies synchronizing in unison (iii)

Flocking and (iv) Fractals, highly scalable self organized systems, such as leaf of a fern, cauliflower and blood vessels. On the other hand, an example of evolution over time, also called as Self Organization [START_REF] Sayama | Complex System Organization Map[END_REF], is the change that occurs within a system. Properties of self organized systems vary from system to system. Most of the systems show properties like positive feedback, negative feedback, leadership, inhibition, synchronization, coordination, cooperation and scalability. Learning is another example of evolution over time. Learning occurs when a system observes its surroundings and performs actions based on what can be beneficial to both surrounding and itself. During learning, a system can thus change its behavior depending on the environment. Nevertheless, evolution is not only restricted to biological systems, but also observed in many non-biological systems. For example, variations of population dynamics over food chain [START_REF] Lotka | Contribution to the Theory of Periodic Reaction[END_REF], self organized criticality [START_REF] Bak | Self-Organized Criticality[END_REF][START_REF] Turcotte | Self-Organized Criticality[END_REF] and human behavior.

The history of self organization can be dated back to the evolution of the universe where the chaotic interaction of the particles gave rise to new structure and phenomena. Through time, this interaction has led the system to evolve and adapt to its surroundings. One of the first examples studied by mankind was the Belousov-Zhabotinsky reaction. In this reaction, the chaotic interactions among the chemicals lead to a pattern formation. During the same period Sir Allan Turing also published his paper on morphogenesis which showed that very simple interactions can lead to very complex patterns. These two pioneering works widely opened the field of self organization and various properties like no central control, emerging structure, complexity, loose coupling, dependence on the environment and high scalability were derived. These properties led researchers to formulate four basic paradigms for a system to be called self organized [START_REF] Prehofer | Self-Organization in Communication Networks: Principles and Design Paradigms[END_REF]. These paradigms are: the elements of the system should use locally available information, implicitly coordinate, have short lived memory and should adapt to the changes in the environment.

Many current technologies are based on the mechanisms applied by the naturally occurring phenomenon. Self organization in a system is applied for various purposes such as configuration, management, adaptability, diagnosis, protection, healing and repair and optimization. However, self organized systems have several limitations, for example, low predictability and slow convergence to the optimal state. The interactions among the elements of the system lead to the formation of a network. Some researchers study the evolution of the network based on the growth and decay in the network [START_REF] Albert | The Diameter of the World Wide Web[END_REF][START_REF] Dorogovtsev | Scaling Behaviour of Developing and Decaying Networks[END_REF][START_REF] Albert | Error and Attack Tolerance of Complex Networks[END_REF][START_REF] Amaral | Classes of Small-World Networks[END_REF][START_REF] Albert | Topology of Evolving Networks: Local Events and Universality[END_REF][START_REF] Krapivsky | Degree Distributions of Growing Networks[END_REF][START_REF] Pennock | Winners don't take all: Characterizing the Competition for Links on the Web[END_REF]. In these studies, the growth and the decay patterns are based on the preferential and probabilistic attachment and detachment of nodes in the network. Some researchers study this effect on different types of underlying networks. Different studies have given many different names to the networks that evolve. Some of the studies refer the evolving network as a Dynamic Network [START_REF] Lerman | Centrality Metric for Dynamic Networks[END_REF][START_REF] Scherrer | Description and Simulation of Dynamic Mobility Networks[END_REF][START_REF] Kuhn | Dynamic networks: Models and Algorithms[END_REF]. Other names given to the evolving networks [START_REF] Borgnat | Evolving Networks[END_REF][START_REF] Grindrod | Evolving Graphs: Dynamical Models, Inverse Problems and Propagation[END_REF][START_REF] Grindrod | Communicability across Evolving Networks[END_REF][START_REF] Grindrod | Social Networks: Evolving Graphs with Memory Dependent Edges[END_REF] are Time Varying Graphs [START_REF] Santoro | Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics[END_REF][START_REF] Casteigts | Time-Varying Graphs and Dynamic Networks[END_REF], Temporal Networks [START_REF] Holme | Temporal Networks[END_REF][START_REF] Pan | Path Lengths, Correlations, and Centrality in Temporal Networks[END_REF] and Adaptive Networks [START_REF] Braha | From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks[END_REF][START_REF] Braha | Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interaction[END_REF].

Evolution also exists in mobile scenario where there are constant changes in the interactions in the network due to mobility. In the context of communication networks, M obile Ad hoc N ET works (M AN ET ) share the properties of the dynamic networks. In M AN ET s, a wireless device is considered as a node in the network with motion capabilities and spatial characteristics. Self organization techniques are used in communication networks mainly to provide better routing mechanisms, resource allocation, network security, synchronization, neighborhood discovery and fault tolerance [START_REF] Dressler | A survey on Bio-Inspired Networking[END_REF].

Social Networking and Small World Networks

One of the key aspects of self organization observed in human community is that of social interactions or social networking. Social groups exist where social ties link individuals with common values and belief.

Social linking between individuals is called as social networking. In 1967, Stanley Milgram [START_REF] Travers | An Experimental Study of the Small World Problem[END_REF] conducted an experiment and analyzed the Average Path Length (AP L) from one individual to another while working on his thesis on small world experiment. In his experiment, individuals were randomly selected and were asked to forward a letter to a target contact. If an individual knew the target contact the letter was directly forwarded after appending the individual's name. However, in the case when an individual did not know the target contact, the individuals were only allowed to forward the letter to one of their connections and append their name. This experiment of Milgram gave rise to the concept of Six degrees of Separation and widely opened the social networking research area. However, many shortcomings of the experiment have been reported since then, for example, (i) some letters did not reach the destination during specified time interval and (ii) the scale of the experiment was small. Consider a graph G(V, E) where V and E represent the set of nodes and edges, respectively, and |V | ∈ N and |E| ∈ Z + . Suppose SP ij is the shortest path between two node i ∈ V and j ∈ V such that |SP ii | = 0. Then AP L of the graph is defined as

AP L = 1 |V |(|V | -1) i,j∈V |SP ij |. ( 2
CC i =    |EN i | |Ni|(|Ni|-1) if directed graph. 2|EN i | |Ni|(|Ni|-1) if undirected graph. (2.2.3)
Consider the the subgraph restricted to the nodes in N i and call it G Ni . The eq. 2.2.3 refers to the fraction of edges in G Ni that actually exist to the maximum number of edges that could have existed in G Ni [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF]. Using CC i , the average CC in the graph is defined as

CC average = 1 |V | i∈V CC i .
(2.2.4) . Let E i be the set of edges connecting node i to other nodes in V . Note that |E i | = k . In Watts and Strogatz model, a node i is uniformly chosen from V . Further, an edge e ij ∈ E i is chosen such that the maximum distance between node i and node j ∈ V is 1 (note that there can be a path from node i to j such that distance between i and j using this path is greater that 1). The chosen edge is then reconnected to a randomly chosen node v with a probability p such that v ∈ V -{i, j}. If e iv is already in E i then the edge is not made. This process continues for all the edges where the maximum distance between i and j is 1. The process is done for all the nodes in the graph. Once all the nodes are considered, the process is again continued with the edges that connect two hop neighbors. The chosen edge is again rewired with probability p to a random vertex satisfying the above condition. This process is continued until all the edges are considered.

In summary, every edge is rewired with a probability p such that there are no duplicate edges. As the rewiring process is dependent on p, the value of p shows an impact on the rewiring process. p = 0 means that no rewiring is done while p = 1 means complete rewiring of the graph is done (cf.

Fig. 2.1)

. A rewiring probability p = 1 leads to a random graph. Note that, as no edge is deleted or added, the number of edges in the resultant graph after rewiring is also |V | k 2 . Watts and Strogatz showed that if 0 < p < 1, then the AP L is drastically reduced while the CC is almost kept intact.

They also showed that regular graphs are highly clustered where the AP L grows linearly with the number of nodes, while for a random network, the growth in AP L is logarithmic. Variation to Watts et al. rewiring model has also been proposed. For example in [START_REF] Newman | Scaling and Percolation in the Small-World Network Model[END_REF][START_REF] Newman | Models of the Small World[END_REF][START_REF] Newman | The Structure and Function of Complex Networks[END_REF], instead of link rewiring, link addition is performed between the nodes with a probability p (cf. Fig. 2.2).

Many researchers [START_REF] Albert | The Diameter of the World Wide Web[END_REF][START_REF] Amaral | Classes of Small-World Networks[END_REF][START_REF] Newman | Scaling and Percolation in the Small-World Network Model[END_REF][START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF][START_REF] Monasson | Diffusion, Localization and Dispersion Relations on Small-World Lattices[END_REF][START_REF] Kulkarni | Evolutionary Dynamics in the Bak-Sneppen Model on Small-World Networks[END_REF][START_REF] Barrat | On the Properties of Small-World Network Models[END_REF][START_REF] Kleinberg | Navigation in a Small World[END_REF][START_REF] Kleinberg | The Small World Phenomenon: An Algorithm Perspective[END_REF][START_REF] Helmy | Small Worlds in Wireless Networks[END_REF][START_REF] Barabási | Scale-Free Networks[END_REF], since showed interest in small world concepts and analyzed many associated characteristics. A brief survey of some of these models is provided in [START_REF] Newman | Models of the Small World[END_REF]. A wireless network, due to its spatial and omnidirectional transmission range characteristics, can be considered as a regular network, and applying rewiring to wireless networks will lead to more randomness. Assuming a spatial wireless network, Helmy [START_REF] Helmy | Small Worlds in Wireless Networks[END_REF] performed small world analysis on wireless networks and showed that rewiring of links had less effect on the structure of the network. Helmy [START_REF] Helmy | Small Worlds in Wireless Networks[END_REF] also showed that the AP L is reduced at a greater rate when shortcuts are 25% to 40% in length of the network diameter and the rate of AP L reduction is more when only 0.2% to 2% shortcut links are created. The reduction rate stabilizes when more than 2% shortcut are created.

On the other hand, Barabási et al. in [42,[START_REF] Barabási | Scale-Free Networks[END_REF] argued that a large network that has small AP L exhibits small world characteristics and can be called as scale free network. In scale free network, the network tends to have few nodes that have high number of connections, called the "hub" nodes, and more nodes that have less number of connections. Information is spread quickly within the network through the hub nodes. Note that the number of connections a node has is also called the degree of a node. Moreover, the degree distribution of nodes in a scale free network follows a power law distribution. Research has proved that information flow through these hub nodes is both advantageous as well as disadvantageous for the network. Despite low AP L, these networks have increased probability of communication failures due to overloading at the hub nodes.

Social Network Analysis and Centrality Measures

Decades of research on graph theory has led researchers to be inspired from social networks and derive many metrics that identify importance of a node in the graph. This field of research commonly came to be known as SN A. In SN A, the concept of centrality is brought up and developed to address topological characteristics of the nodes in the graph. The centralities, depending on the parameters they use, can be both local as well as global. Some examples of global centrality measures include socio-centric betweenness [START_REF] Freeman | A Set of Measures of Centrality Based on Betweenness[END_REF][START_REF] Freeman | Centrality in Social Networks Conceptual Clarification[END_REF] and closeness centralities [START_REF] Freeman | Centrality in Social Networks Conceptual Clarification[END_REF]. The egocentric betweenness centrality [START_REF] Everett | Ego Network Betweenness[END_REF][START_REF] Daly | Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs[END_REF] is an example of local centrality measure. All the above centrality measures are well-defined for static networks. Recently, centrality measures in dynamic conditions have also been proposed [START_REF] Kim | Centrality Prediction in Dynamic Human Contact Networks[END_REF] where the field of research is popularly known as Dynamic Network Analysis (DN A).

Socio-Centric Betweenness Centrality

Socio-centric betweenness centrality [START_REF] Freeman | A Set of Measures of Centrality Based on Betweenness[END_REF][START_REF] Freeman | Centrality in Social Networks Conceptual Clarification[END_REF] is the measure of number of shortest paths passing through the node thereby expressing the most important node in the network through which most communications take place. Determination of the shortest path requires the knowledge about the network. Socio-centric betweenness is a global measure as it is computed using shortest paths.

Nodes with high degree and nodes that are acting as the bridge nodes tend to have high sociocentric betweenness. Consider a graph G(V, E) with set of nodes V and set of edges E such that |V | ∈ N and |E| ∈ Z + . Let σ uv be the number of all shortest paths between two nodes u ∈ V and v ∈ V -{u}. Let σ i uv be the number of shortest paths between u and v passing through i ∈ V such that u = v = i. Socio-centric betweenness of a node i ∈ V is defined as

BC i = u =v =i∈V,σuv>0 σ i uv σ uv . (2.2.5)
Variations to Socio-centric betweenness centrality have also been proposed. These include Egocentric Betweenness Centrality, Flow Betweenness Centrality (F BC) [START_REF] Freeman | Centrality in Valued Graphs: A Measure of Betweenness Based on Network Flow[END_REF] that measures the importance of a node based on traffic flow in the network, Routing Betweenness Centrality (RBC) [START_REF] Dolev | Routing Betweenness Centrality[END_REF] that considers paths resulting from routing strategies and Wireless Flow Betweenness Centrality [START_REF] Banerjee | Self-Organization of Wireless Ad Hoc Networks as Small Worlds using Long Range Directional Beams[END_REF][START_REF] Banerjee | A Self-Organization Framework for Wireless Ad Hoc Networks as Small Worlds[END_REF], explained further in appendix A.

Egocentric Betweenness Centrality

Aiming to compute the Betweenness centrality using local properties, [START_REF] Everett | Ego Network Betweenness[END_REF][START_REF] Daly | Social Network Analysis for Routing in Disconnected Delay-Tolerant MANETs[END_REF] proposed Egocentric Betweenness Centrality measure (EBC). In a graph G(V, E) with the set of nodes V and the set of edges E with no self edges, |V | ∈ N and |E| ∈ Z + . Let N i be the set of one-hop neighbors of

i ∈ V , 0 ≤ |N i | ≤ |V | and N i ⊂ V .
Let A i be the adjacency matrix formed by all nodes in N i . Each element, (A i ) jk , in A i represents the state (either 0 or 1) of the edge between two nodes j and k in N i . The maximum distance between two nodes in N i is equal to two hops as the nodes in N i can be connected via i. The number of two hop paths between a pair of nodes in N i is given by the corresponding element of

A 2 i . Let x jk = [1 -(A i ) jk ](A 2 i ) jk .
When the path length between j and k is more than one hop, x jk will provide number of paths between j and k that are of length 2 hops. However, if there is a one-hop path between j and k, then x jk = 0. Everett et al. in [START_REF] Everett | Ego Network Betweenness[END_REF] defined the Egocentric Betweenness of the node i as

EBC i = 1 2 j,k∈Ni,j =k,x jk =0 1 x jk . ( 2
EBC i = (|Ni|-1)(|Ni|-2) 2 .
Marsden in [START_REF] Marsden | Egocentric and Sociocentric Measures of Network Centrality[END_REF] performed an empirical study to find the relation between the two types of Betweenness, Socio-Centric and Egocentric. He found that Egocentric Betweenness is strongly correlated with Socio-Centric Betweenness and can be used when global network information is missing.

Closeness Centrality

Closeness Centrality (CLC) [START_REF] Freeman | Centrality in Social Networks Conceptual Clarification[END_REF] is used to measure how central a node is in the network. Closeness centrality is also a way to measure how quickly dissemination of information, in terms of hops, will take place through the node. Closeness Centrality is the inverse of the sum of the shortest path lengths between a node and all other nodes in the graph. Consider a graph, G(V, E) with set of nodes V and set of edges E such that |V | ∈ N and |E| ∈ Z + . Let SP ij be the shortest path between node i ∈ V and j ∈ V -{i} such that |SP ii | = 0, the CLC of the node i is defined as

CLC i = 1 j∈V -{i} |SP ij | . (2.2.7)
A node with the highest Closeness Centrality is also the centroid node in the graph. As all the centrality measures convey different information, it is not necessary that a node that has a high value for one centrality measure also has high values for the other centrality measures. Apart from Socio-centric Betweenness and Closeness Centrality, many other types of centrality measures, such as Eigen Value Centrality [START_REF] Newman | The Mathematics of Networks[END_REF], Katz Centrality [START_REF] Katz | A New Status Index Derived from Sociometric Analysis[END_REF], Spectral Centrality and centrality measure in weighted networks [START_REF] Opsahl | Node Centrality in Weighted Networks: Generalizing Degree and Shortest Paths[END_REF] also exist but we refrain from defining them as we are only interested in closeness centrality and betweenness centrality. A comprehensive survey of some of the centrality measures is provided in [START_REF] Katsaros | Social Network Analysis Concepts in the Design of Wireless Ad Hoc Network Protocols[END_REF].

Dynamic Centrality Measures

Recently, dynamic version of the centrality measures have been proposed using temporal graphs [START_REF] Lerman | Centrality Metric for Dynamic Networks[END_REF][START_REF] Grindrod | Communicability across Evolving Networks[END_REF][START_REF] Santoro | Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics[END_REF][START_REF] Pan | Path Lengths, Correlations, and Centrality in Temporal Networks[END_REF][START_REF] Kim | Temporal Node Centrality in Complex Networks[END_REF]. These measures mainly use temporal distance in order to formulate the centrality measures.

Definition 2.2.1. A temporal (dynamic) graph is a graph that changes with time. The characteristics of temporal graph are studied using a group of discrete snapshots of the graph each taken after Recently, [START_REF] Santoro | Time-Varying Graphs and Social Network Analysis: Temporal Indicators and Metrics[END_REF][START_REF] Pan | Path Lengths, Correlations, and Centrality in Temporal Networks[END_REF][START_REF] Kim | Temporal Node Centrality in Complex Networks[END_REF] defined Temporal Shortest Path (T SP ), a variation of shortest path for temporal graphs, as the path that takes the minimum number of time steps to send the information to the destination. The minimum number of time steps to any node is called the Temporal Distance.

Consider a graph snapshot, G t (V, E t ), with set of nodes V = {i, j, u, v} and set of edges E t at time t such that |E t | ∈ Z + . Note that V is fixed over all time instants. Let i t , j t , u t and v t be the time dependent representations of the nodes in V (cf. Fig. 2.3). To compute the temporal distance, the Aggregated Graph is generated as follows. The nodes i t , j t , u t and v t are vertically arranged at each time step t (cf. Fig. 2.3). If there is an edge between two nodes a and b in G t (V, E t ), then there are two directed edges in the aggregated graph, namely, an edge from a t to b t+∆t and an edge from b t to a t+∆t . This step is performed because, if a node has a packet to transmit at time t, the neighbor nodes in G t (V, E t ) will only receive the packet at the next time instant (t + ∆t). It is also assumed that the nodes keep the packet with them and each transmission is completed in a single time step. Fig. 2.3 shows a representation of aggregated graph generated from snapshot graphs for the period t = 0 to t = 3. Let G ′ be the resultant aggregated graph (Cf. Fig. 2.3). Suppose ∆t = 1. Let node i generates a packet at time t = 0 that has to be sent to node v. Then the T SP between i and v

is (i 0 → j 1 → u 2 → v 3 ), i.e.
, it takes 3 time steps to send the packet to the destination. Similarly, if node v generates a packet at time t = 0 to send to node u, then one of the T SP s that can be followed is (v 0 → j 1 → u 2 ), i.e., it takes 2 time steps to reach to the destination. Further, if node j generates a packet at time t = 2 and wants to send it to v then it will not be able to do so because there is no path from j 2 to v. in [START_REF] Kim | Temporal Node Centrality in Complex Networks[END_REF] defined T SP between two nodes i and j as

Let i * be an instance of the node i ∈ V at time t = * . Let G ′ (V ′ , E)
T SP ij = arg min t<x≤t ′ {(i t → . . . → k x-1 → j x )}. (2.2.8)
Note that due to the temporal nature, the graph G ′ is a directed graph. Also note that T SP ij = T SP ji and |T SP ij | ∈ N for j ∈ V -{i}. Further, if there is no path between i and j in the time interval [t, t ′ ] then |T SP ij | is considered as ∞. This is because T SP is defined based on the time steps and it is assumed that in time → ∞ the nodes i and j will be connected.

Let Y be the set of subintervals of the time interval [t, t ′ ] such that the end time of each subinterval is t ′ but the starting time is strictly less than t ′ , i.e.,

Y = {[k, t ′ ] | t ≤ k < t ′ }.
Let T SP y ij be the T SP between i and j in the time interval y ∈ Y . Temporal Closeness Centrality (T CLC) of a node i in the time interval [t, t ′ ] is defined as

T CLC i = j∈V -{i}   y∈Y 1 |T SP y ij |   .
(2.2.9)

The eq. 2.2.9, states to sum all the temporal paths between i and j which have occurred over

time period [t, t ′ ]. Further, as 0 < |T SP ij | < ∞, when |T SP ij | → ∞, it is assumed that 1 ∞ = 0 and thus 1 |T SPij | = 0.
Consider Y as discussed before and σ i uv as the number of all temporal shortest paths between two nodes in u, v ∈ V passing through i ∈ V such that u = v = i. Let σ uv be the number of temporal shortest paths between two nodes u, v ∈ V such that u = v and σ i uv ≤ σ uv . Temporal Betweenness Centrality (T BC) of a node i is defined as

T BC i = u =v =i∈V,σuv>0   y∈Y σ i uv σ uv   .
(2.2.10)

T D i = t ′ -∆t t N t i t ′ -t -∆t . (2.2.11)
In [START_REF] Kim | Centrality Prediction in Dynamic Human Contact Networks[END_REF] Kim et al. proposed how centrality measures can be predicted using aggregated graphs over time rather than using T SP . In the algorithm, the prediction changes every instant as a new snapshot of the graph is aggregated to the previous graphs. [START_REF] Balanis | Antenna Theory-Analysis and Theory[END_REF][START_REF] Bettstetter | How does Randomized Beamforming Improve the Connectivity of Ad Hoc Networks?[END_REF] provides an extensive study of antenna models. Consider an antenna with elevation θ and azimuth φ such that θ ∈ [0, π] and φ ∈ [0, 2π]. Let u(θ, φ) be the radiation power per unit solid angle. For a lossless antenna, the gain, g(θ, φ) is defined as

Antenna Model and Beamforming

g(θ, φ) = u(θ, φ) 1 4π 2π 0 π 0 u(θ, φ)sinθ dθ dφ . (2.3.1)
In wireless networks, long links are created using beamforming antenna. A beamforming antenna is an antenna array that consists of M antenna elements (AE)s. Consider an antenna array with M AEs such that M ∈ N where all AEs are isotropic radiators with the same phase shift, γ, between them. Individually, each AE has an omnidirectional radiation pattern. When one AE is used there is no superposition of the radiation. This leads to an omnidirectional radiation pattern. However, when more than one AEs are used, there is a constructive and destructive superposition of the radiation due to the phase shift between the AEs and directional radiation pattern is observed.

This directional pattern consists of a main lobe and secondary lobes. The main lobe is obtained in where ψ = 1 2 ( 2π∆ λ cos θ + γ). The radiation intensity is however independent of φ because of the rotational symmetry of the setup about the z axis [START_REF] Bettstetter | How does Randomized Beamforming Improve the Connectivity of Ad Hoc Networks?[END_REF]. We thus denote g(θ, φ) as g(θ). For a U LA model, the boresight direction is defined as B b = ± arccos -γλ 2π∆ . In order to achieve maximum gain in the direction of B b , γ is set to γ = -2π ∆ cos B b . That is, given B b the phase shift between AEs is calculated. This simplifies ψ to ψ = π∆(cos θcos B b )/λ. Assuming ∆ = λ/2 as a common choice, g(θ) is defined as

g(θ) = 1 M sin(M ψ) sin ψ 2 . (2.3.2)
It is observed that the maximum gain achieved for the U LA antenna model only depends on the number of AEs used while it is independent of the boresight direction (cf. Fig. 2.4). Note that the gain can also be expressed in terms of the maximum gain achieved. In such case, the normalized gain is given by ĝ(θ) = g(θ) max{g(θ)} .

Let the transmitter and receiver gains be g t and g r , respectively. Let p t be the signal transmission power and p r be the power with which the signal is received. Given a propagation environment, characterized by the path loss exponent α, in order to have a link setup between two nodes and for a transmitted signal to be correctly received by a node located at a distance s, p r is defined as

p r = p t g t g r s α > p r0 (2.3.3)
where p r0 is a threshold power called as receiver sensitivity. We assume that all nodes have the same p t and p r0 .

In communication networks, Multiple Input Multiple Output (M IM O) technology as described in IEEE 802.11n represents a way to achieve beamforming using multiple antennas. However, in M IM O, beamforming can be achieved at both receiver and transmitter. In the dissertation, we only focus on achieving beamforming at the transmitter side. Thus we assume g r = 1 as nodes always receive in omnidirectional mode. Further, we assume network setup in two dimensions, specifically the yz plane, which implies φ = ±π/2. Moreover, as in the dissertation our objective is to demonstrate the improvement that is to be achieved in the network performance when beamforming is used over that of omnidirectional antenna, for simplicity, we chose free space propagation model with path loss exponent α = 2. In propagation environment other than free space there will be obstacles along certain directions and the transmission range cannot be increased in those directions even using directional antenna. Thus our basic premise of the tradeoff between range and angular coverage that exists between directional and omnidirectional antenna will no longer be valid. Hence, we assume free space propagation environment. For more realistic environments, the algorithms described in the dissertation can be studied using 2 < α ≤ 4.

Nevertheless, our objective is to demonstrate the improvements that is achieved in the network performance when beamforming is used over that of omnidirectional antenna. Hence, it is necessary to present the relation between the beam length in the directional case and that of the transmission range in the omnidirectional case. Consider an omnidirectional transmission range, r ∈ R + , which is achieved by the use of one AE. The maximum beam length, B l , in the B b direction when M AEs are used is equal to r × α √ M for the U LA model. Note that when α = 2, B l = r × √ M .

In wireless ad hoc networks, beamforming using U LA and U CA model has been well studied. Beamforming techniques using these antenna models include Random Direction Beamforming (RDB) [START_REF] Bettstetter | How does Randomized Beamforming Improve the Connectivity of Ad Hoc Networks?[END_REF][START_REF] Vilzmann | Hop Distances and Flooding in Wireless Multihop Networks with Randomized Beamforming[END_REF]. Bettstetter et al. [START_REF] Bettstetter | How does Randomized Beamforming Improve the Connectivity of Ad Hoc Networks?[END_REF] studied the use of RDB with the path probability (cf. Definition 2.3.1 below) to improve the connectivity in the wireless networks. They showed that path probability between two nodes is increased using RDB. Other works on beamforming include [START_REF] Vilzmann | Low Complexity Beamforming Techniques for Wireless Multihop Networks[END_REF][START_REF] Kiese | On Connectivity Limits in Ad Hoc Networks with Beamforming Antennas[END_REF][START_REF] Yu | Connected Coverage in Wireless Networks with Directional Antennas[END_REF][START_REF] Li | Asymptotic Connectivity in Wireless Ad Hoc Networks Using Directional Antennas[END_REF]. Considering all nodes beamforming, [START_REF] Bettstetter | How does Randomized Beamforming Improve the Connectivity of Ad Hoc Networks?[END_REF][START_REF] Vilzmann | Hop Distances and Flooding in Wireless Multihop Networks with Randomized Beamforming[END_REF][START_REF] Vilzmann | Low Complexity Beamforming Techniques for Wireless Multihop Networks[END_REF][START_REF] Kiese | On Connectivity Limits in Ad Hoc Networks with Beamforming Antennas[END_REF][START_REF] Yu | Connected Coverage in Wireless Networks with Directional Antennas[END_REF][START_REF] Li | Asymptotic Connectivity in Wireless Ad Hoc Networks Using Directional Antennas[END_REF] addressed connectivity very well but do not discuss the impact on the AP L and the CC.

path probability = ν i |V i |(|V i | -1) |V |(|V | -1) . ( 2
In [START_REF] Durrani | Connectivity of Wireless Ad Hoc Networks with Random Beamforming: An Analytical Approach[END_REF][START_REF] Zhou | Connectivity Analysis of Wireless Ad Hoc Networks With Beamforming[END_REF], authors study connectivity metrics with few nodes beamforming and show that using only few AEs connectivity is increased. However, again [START_REF] Durrani | Connectivity of Wireless Ad Hoc Networks with Random Beamforming: An Analytical Approach[END_REF][START_REF] Zhou | Connectivity Analysis of Wireless Ad Hoc Networks With Beamforming[END_REF] lacks impact on CC. Table 2.1 illustrates a comparison between some of these studies.

Lateral Inhibition

Lateral Inhibition is defined as the ability of a node to restrict its neighbors from performing a certain task. Various examples of Lateral Inhibition are found in biology. An example of Lateral Inhibition observed in biological process is where cells on the tissues of animals skin, depending on the neighbor properties, decide either to grow a hair or not to grow a hair. Lateral Inhibition ensures that hairs are grown equidistant from each other and helps in producing regular patterns throughout the surface. When a cell grows a hair it inhibits its neighbors from growing a hair, resulting into equally spaced uninhibited cells [START_REF] Lawrence | The Making of a Fly: The Genetics of Animal Design[END_REF]. Lateral Inhibition thus creates clusters where the cluster heads are the uninhibited nodes distributed uniformly over the region. The Lateral Inhibition process is also regarded as the identification of the maximal independent set (M IS).

Consider a graph G(V, E) with set of nodes V and set of edges E such that |V | ∈ N and |E| ∈ Z + .

A maximal independent set, S, consists of nodes in V such that no two nodes in S are neighbors.

Addition of any node from V -S to S will break the property of independence. Note that the above property gives rise to another property whereby all nodes in V -S are connected to a node in S.

M IS is often used for clustering of nodes in the network.

In a decentralized environment, probabilistic approaches are used to select M IS. Here, the probability of getting selected to join nodes in S depends on the number of neighbors that are not connected to nodes in S. Moreover, the M IS algorithms have high message complexity and assume the knowledge of the network [START_REF] Afek | A Biological Solution to a Fundamental Distributed Computing Problem[END_REF]. These features make it tough for the applications of M IS in the wireless ad hoc network.

Nagpal et al. [START_REF] Nagpal | An Algorithm for Group Formation in an Amorphous Computer[END_REF][START_REF] Nagpal | Engineering Amorphous Computing Systems[END_REF] described a simple algorithm through which Lateral Inhibition is achieved with less message complexity and without the knowledge of the network. Consider G(V, E) as defined above. A node i ∈ V is said to be connected to another node j ∈ V if the Euclidean distance between i and j is less than or equal to r where r is the transmission range of node i such that r ∈ R + . Suppose that all nodes have same transmission range r and all nodes are autonomous. At the start of the algorithm each node is assigned two different values. First, a same random value

R 1 such that R 1 ∈ R + and R 1 > 0 is assigned to all the nodes. Second, each node is assigned a random value R 2 such that R 2 = [0, R 1 )
. R 1 allows the algorithm to be run for R 1 time steps after which all nodes are either inhibited or uninhibited. The algorithm assumes discrete time steps. At each time step all nodes decrement R 1 by 1 and check if R 2 = 0 or not. If R 2 = 0, the node checks if an interrupt is received from the neighbors. If an interrupt is not received the node decrements R 2 by 1. However, if the interrupt is received the node exits the algorithm and becomes inhibited.

However, if for a node R 2 becomes 0 before getting the interrupt, the node broadcasts the interrupt signal to all its neighbors and becomes uninhibited. If an interrupt is received from two or more neighbors the inhibited node remains inhibited. Note that the inhibited node does not send any signal to other nodes in the network. The whole process runs for R 1 time steps. After running the algorithm, the nodes are either inhibited or uninhibited. The set of uninhibited nodes form the set S in the M IS. As an uninhibited node inhibits all its neighbor, the distance between two uninhibited nodes mainly lies between r to 2r hops where r is the transmission range of the nodes. However, the algorithm can be extended to h hops [START_REF] Nagpal | Engineering Amorphous Computing Systems[END_REF] where h ∈ N.

Flocking

In nature, grouping is observed in many social living beings like birds, cattle, fishes and humans. A group of birds assembled together is called a flock. In nature it is observed that the flocks remain connected and move together. While moving, the birds exhibit a behavior which is called flocking.

Flocking is thus a collective behavior of the birds that move together. Flocking was first modeled by Reynolds in order to simulate the collective behavior of the birds in motion [START_REF] Reynolds | Flocks, Herds and Schools: A Distributed Behavioral Model[END_REF]. In the model, each bird was considered as a boid. We call them as the nodes. In flocking, each node is considered to be autonomous and has three behavioral rules (a) Alignment (b) Separation and (c) Cohesion.

Definition 2.5.1. The Alignment rule states that if a node i is moving in different direction than that of the average direction of its neighbors, the node has to change its direction of motion and orient towards the average direction of motion of its neighbors to match that of its neighbors (cf. Fig. 2.5(a)). The Alignment rule thus consists of a decision whether to change the direction or not. As a consequence of this decision, the action for a node is to determine the new direction of motion and to move in that direction. Note that due to the definition of the alignment rule, it is independent of the magnitude of the velocity and the location of the node. Let N i be the set of neighbors of node i. Let d j be the direction of motion of a neighbor j ∈ N i . The new direction of motion of i is defined as

d i = j∈Ni d j |N i | .
Definition 2.5.2. The Separation rule states that a node should maintain a certain minimum distance with its neighbors (cf. Fig. 2.5(b)). Consider a node i and its neighbor j. Let D ij be the Euclidean distance between two nodes such that D ij ∈ R + . Let D min be the minimum required

separation distance such that D min ∈ R + . Separation rule states that D ij ≥ D min . If D ij < D min ,
then the node i should move away from node j either by slowing down or by moving in a different direction. Thus, Separation rule consists of a decision by a node whether to move apart. As a consequence of this decision, the action of the node is to either slow down or change the direction of motion. The separation rule ensure that there is no overcrowding at a given location and nodes do not collide. If D min is small, the nodes will be overcrowded at a given location and there will be high number of collisions. However, if D min is large the nodes will be too far apart. Among all the three Flocking rules, the Separation rule is of the highest priority [START_REF] Couzin | Effective Leadership and Decision-Making in Animal Groups on the Move[END_REF].

The Separation rule is thus beneficial towards autonomous sensor deployment in the region where the minimum distance between two nodes should satisfy D min > 0. Kadrovach et al. [START_REF] Kadrovach | A Particle Swarm Model for Swarm-Based Networked Sensor Systems[END_REF] used the Separation rule for efficient placement of nodes to maximize the coverage area.

Definition 2.5.3. The Cohesion rule states that if a node is far from its neighborhood it should move towards the centroid of the neighborhood to remain connected to all of its neighbors (cf. Fig.

2.5(c))

. The cohesion rule thus consists of a decision whether to move towards the centroid of the neighborhood or not. As a consequence of this decision, the node should increase its velocity and should move in the direction of centroid. Let N i be the set of neighbors of node i. Let (p j x , p j y , p j z ) be the position of a neighbor j ∈ N i . The new position i should move to is defined as

(p i x = j∈Ni p j x |N i | , p i y = j∈Ni p j y |N i | , p i z = j∈Ni p j z |N i |
). Cohesion relates to the tendency of a node to remain as close to its neighbors as possible and do not stray. It also implies the group's strength to stay connected.

Note that the rules are applied at each instant. Further, recently, researches have revealed that flocking can be used to solve various problems in wireless networks. For example, Antoniou et al. [START_REF] Antoniou | Congestion Control in Wireless Sensor Networks Based on the Bird Flocking Behavior[END_REF] used flocking to provide efficient congestion control mechanism by computing the congestion at the neighbor nodes. In our case, we use analogy with Flocking rules in order to determine which nodes should beamform and in which direction the beams should be directed.

Non-Uniform Distribution of Nodes

Much of the research in wireless networks considers uniform node deployment. However, in reality, non-uniformity exists. Bettstetter et al. [START_REF] Bettstetter | An Inhomogeneous Spatial Node Distribution and its Stochastic Properties[END_REF] proposed the use of thinning process to generate a non-uniform node deployment. A . An edge between i ∈ V and j ∈ V is created if j is within the Euclidean distance, r ∈ R + of the node i. The algorithm prunes the nodes in the deployment using two parameters, r b and N min such that r b ∈ R + and N min ∈ Z + .

In the algorithm, a new graph G ′ (V, E ′ ) is generated such that every pair of nodes in V that are within a distance r b are connected by an edge. Let N i be the neighborhood

of node i ∈ V in the new graph G ′ such that 0 ≤ |N i | ≤ |V | and N i ⊂ V .
A check on the number of neighbors is then performed on all the nodes. For all node i ∈ V the algorithm checks if |N i | < N min . If the condition is true, then the node is marked as to be removed. Finally, when all the nodes have been checked for the condition, the nodes are then removed from the original graph G to obtain the final graph G * (V * , E * ) (cf. Fig. 2.7). Note that the algorithm is only run once and the deployment achieved after the thinning process is used for non-uniform deployment. Also note that if N min = 0, then the pruned graph will have no nodes left. However, if N min < min{|N i |} and r b = r then all nodes will remain in the pruned graph. The expected number of nodes remaining in the graph is

given by

E(|V * |) = |V | 1 - Γ(Nmin,ρr 2 b π) (Nmin-1)!
. Note that the probability of a node being removed is p = Γ(Nmin,ρr 2 b π)

(Nmin-1)! . However, this method faces with border effect, where nodes near the border are removed as the number of neighbors are less. This limitation of the algorithm is removed by using wrap around mechanism. However, we do not consider such case and consider thinning process with boarder effect to get the non uniform deployment.

Schilcher et al. [START_REF] Schilcher | Measuring Inhomogeneity in Spatial Distributions[END_REF], following the work of Bettstetter et al., formulate the degree of non-uniformity of this pruned network. Consider a uniform distribution of a set of nodes V in an area A. A grid of size a × a where a ∈ N is placed on the area. Let A i be the area of the i th square in the grid such that A = a 2 i=1 A i . Each subarea A i has a set V i of nodes associated with it. The expected number of nodes for all A i s is equal to |V | a 2 . A deviation from this quantity is measured as the non-uniformity in the deployment. Let V * denote the set of nodes that are left after thinning. Each subarea A i will now have V * i nodes associated with it. Non-uniformity is defined as

h a = 1 2|V | a 2 i=1 absolute |V * i | - |V | a 2 ,
where absolute(x) denotes the absolute value of x. Note that maximum non-uniformity is achieved when all nodes are located in one square in the grid. The normalization constant 1 2|V | is chosen such that lim a→∞ h a = 1.

Further, many other non-uniform deployment strategies also exist [START_REF] Le Boudec | The Random Trip Model: Stability, Stationary Regime, and Perfect Simulation[END_REF][START_REF] Hsu | Modeling Time-Variant User Mobility in Wireless Mobile Networks[END_REF][START_REF] Riihijarvi | Influence of Node Location Distributions on the Structure of Ad Hoc and Mesh Networks[END_REF][START_REF] Hu | Heterogeneous Community-Based Mobility Model for Human Opportunistic Network[END_REF][START_REF] Aitsaadi | Artificial Potential Field Approach in WSN Deployment: Cost, QoM, Connectivity and Lifetime Constraints[END_REF]. But in this dissertation, we use the thinning process proposed by Bettstetter et al. in [81] because of its simplicity.

Human Mobility

Recent analysis on the human mobility dataset reveals many different properties for human mobility.

These properties include spatial properties like jump length and radius of gyration. Definition 2.7.1. A jump length x such that x ∈ R + is the distance moved by a person in a given time.

Definition 2.7.2. The radius of gyration, r g , for a person is defined as the root mean square distance of the jump length from the mean jump length. Consider X to be the set of all jump lengths for a person. The mean jump length is defined by x = 1 |X| i∈X i. Thus r g is defined as

r g = 1 |X| i∈X (i -x) 2 .
Note that r g will be different for different person.

Consider x as the jump length, x min as the minimum jump length such that x min ∈ R + and

x min > 0, α as the power law exponent such that α ∈ R + , β as a cutoff value such that β ∈ R + and β > 0, λ = Using statistical analysis of mobility traces, Gonzalez et al. [START_REF] González | Understanding Individual Human Mobility Patterns[END_REF] observed that the distribution of x follows the truncated power distribution which is defined as [START_REF] Clauset | Power-Law Distributions in Empirical Data[END_REF] p

(x) =    λ 1-α Γ(1-α,λxmin) x -α e -λx if x ≥ x min , 0 otherwise. (2.7.1)
Truncated power law distribution means that for small values of x the distribution follows a power law, for values of x sufficiently larger than β it follows an exponential distribution and this change in behaviour or cutoff occurs approximately at β. The exponential cutoff observed in the distribution of the jump length is mainly due to boundary effects and limited sampling of the mobility data [START_REF] Mossa | Truncation of Power Law Behavior in Scale-Free Network Models due to Information Filtering[END_REF].

In particular, [START_REF] González | Understanding Individual Human Mobility Patterns[END_REF] noted that human movement is limited within the radius of gyration r g for 67% of the time. Human mobility has been closely related to the small world behavior. The few long jumps are mapped to long links while short jumps to regular links. This property of human mobility thus helps in the dissemination process. However, some researchers have argued that long jumps could cause disconnections and hence mobility could restrict the dissemination process. This mainly happens in low density scenarios.

For the human mobility dataset obtained for the region of the United States, the truncated power law distribution parameters for the jump length are α = 1.75 ± 0.15, x min = 1.5km and a variable β [START_REF] González | Understanding Individual Human Mobility Patterns[END_REF]. The dataset used to obtain these parameters contains location coordinates of users recorded after each 2hrs. The dataset had low spatial resolution. In the dataset, the location coordinates are not the exact location coordinates of the person but they are the locations of the mobile towers they are associated with. If a user is in the region served by the mobile tower, the coordinates of the mobile tower is recorded in the dataset. The average distance between the mobile towers is found to be 3km. It is revealed that the truncated power law distribution [START_REF] González | Understanding Individual Human Mobility Patterns[END_REF] is followed by r g as well.

The truncated power law distribution parameters for r g are α = 1.65 ± 0.15, x min = 5.8km and β = 350km. Note that the distribution of r g is computed using r g 's for all the people in the dataset.

Recently, it is also noted that other than spatial properties many other properties are associated to the human mobility. These include temporal properties like the pause time [START_REF] Song | Modelling the Scaling Properties of Human Mobility[END_REF].

Definition 2.7.3. The Pause Time is defined as the time a person stays at a given location.

For a similar dataset as used by [START_REF] González | Understanding Individual Human Mobility Patterns[END_REF], Song et al. in [START_REF] Song | Modelling the Scaling Properties of Human Mobility[END_REF] revealed that the distribution of pause time also follows the truncated power law distribution. However, the difference in the datasets is the time interval (1hr) between the records. The truncated power law distribution parameters for the pause time are α = 0.8 ± 0.1, x min = 1hr and β = 17hr. x min = 1hr because the location of the person is recorded after each 1hr.

Apart from spatio-temporal properties, human mobility has also been associated to temporal behavioral characteristics in form of periodic movement, aperiodic movement and sporadic movement.

Periodic movement corresponds to the case when a node traverses through the same sequence of locations periodically over time. In aperiodic movement the sequence of locations traversed before returning to a place may not be fixed whereas sparodic movement corresponds to the case when the sequence of locations traversed is never repeated. Further, human mobility also show spatial behavioral characteristics like centric, orbital, and random movement [START_REF] Karamshuk | Human Mobility Models for Opportunistic Networks[END_REF].

In another recent research [START_REF] Csáji | Exploring the Mobility of Mobile Phone Users[END_REF], it is shown that the jump lengths for the country of Portugal follows a lognormal distribution thereby proving that the the distribution of the jump length depends on the region and boundaries associated to the region. Also note that human mobility pattern can be used to generate non-uniformity in the network. In an interaction network or a social network, application of mobility leads to links being intermittent thereby causing network structure to change over time.

As explained before, characteristics of such networks can be studied using temporal snapshots of the network.

Mobility models that use truncated power law nature of spatio-temporal properties of human mobility include [START_REF] Lee | SLAW: A New Mobility Model for Human Walks[END_REF][START_REF] Lee | SLAW: Self-Similar Least-Action Human Walk[END_REF][START_REF] Rhee | On the Levy-Walk Nature of Human Mobility[END_REF]. Consider a discrete time mobility model. Consider a person. We call the person as a node. Consider a sufficiently large square area with area A such that A ∈ R + .

Within the bounds of the area, the mobility of the node is defined by the tuple (x,θ,t p ) where x is the distance moved or the jump length such that 0 < x ≤ √ A, θ is the direction of the motion such that θ ∈ [0, 2π] and t p is the pause time such that t p ≥ 0. At the beginning of each step a node computes the values for the tuple. x and t p are calculated from the truncated power law distribution while θ is uniformly chosen from [0, 2π]. Let each jump be completed in 1 time step. Note that for extracting a sample, x, from a truncated power law distribution, the sample is first extracted from an exponential distribution and then the sample is accepted with a probability p = ( x xmin ) -α [START_REF] Clauset | Power-Law Distributions in Empirical Data[END_REF]. If t p > 0, it means that the node stays at the current location for t p time steps before it moves to some other location. During this period, the jump length x and the direction θ are not sampled [START_REF] Rhee | On the Levy-Walk Nature of Human Mobility[END_REF].

t p = 0 means that the node will change its position in the next time step.

For our mobility model we assume that t p = 0. Further, we assume that x min = 1 and β < √ A.

Note that when a node is at the boundary, choosing θ can cause the node to move out of the boundary of the given area. If such a situation happens θ is again computed until the jump is within the bounds of the area. Also note that if the jump length itself is large enough that it cannot be within the area bounds then the jump length is again sampled from the truncated power law distribution.

Stability Measures

Stability is complementary to the change occurring in the system. It is the measure that determines how much stable a system is in a dynamic environment. Stability can be calculated by determining the percentage change in the system. Stability is defined at different scales, for example, in a temporal graph, stability is defined for the graph, for the nodes and for the links in the graph. A temporal graph is characterized by a group of discrete snapshots of a graph each taken after ∆t time step [START_REF] Kim | Temporal Node Centrality in Complex Networks[END_REF]. The stability measures are thus calculated using different snapshots.

For the stability of the graph, in [START_REF] Pincombe | Detecting Changes in Time Series of Network Graphs using Minimum Mean Squared Error and Cumulative Summation[END_REF][START_REF] Jurman | An Introduction to Spectral Distances in Networks[END_REF] the authors use the distance between the Laplacian spectrum defined by the eigen values of the Laplacian matrix of the snapshots. In other studies, [START_REF] Braha | From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks[END_REF][START_REF] Braha | Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interaction[END_REF][START_REF] Hill | Dynamic Model of Time-Dependent Complex Networks[END_REF], for each snapshot, the authors ranked the nodes based on their degrees to compute the stability of the graph. The top x% of the nodes are then selected from each snapshot and common nodes occurring in the selection are found. The number of common nodes provided the stability of the graph.

In [START_REF] Hanneke | Discrete Temporal Models of Social Networks[END_REF][START_REF] Tang | Small-World Behavior in Time-Varying Graphs[END_REF] the authors use the adjacency matrix of the snapshots to define the stability of a link.

In [START_REF] Hanneke | Discrete Temporal Models of Social Networks[END_REF] the authors proposed that a link is stable if its state did not change in the considered time frame while [START_REF] Tang | Small-World Behavior in Time-Varying Graphs[END_REF] argued that the links that maintained their status of 0 should not be considered.

Further, link stability can also be inferred from the entropy of the link [START_REF] Zayani | Improving Link Prediction in Intermittently Connected Wireless Networks by Considering Link and Proximity Stabilities[END_REF]. Other ways of measuring stability includes the use of similarity measures. A high similarity means that two systems are similar and change that has occurred in the system over time is small. A survey of similarity measures is provided in [START_REF] Lu | Link Prediction in Complex Networks: A Survey[END_REF].

We now provide a brief overview of some stability measures.

Similarity

Similarity is a well defined concept in data mining context. Representing a system as a vector, many similarity measures have been defined to determine the similarity between two vectors. These methods include Euclidian Distance, Cosine Similarity, Jaccard Coefficient, Pearson correlation, etc [START_REF] Lu | Link Prediction in Complex Networks: A Survey[END_REF]. A high similarity means that two systems are similar and change that has occurred in the system over time is small. Consider a graph, G(V, E) with set of nodes V and set of edges

E such that |V | ∈ N and |E| ∈ Z + . Let N t i be the neighborhood of node i ∈ V at time t such that 0 ≤ |N t i | ≤ |V | and N t i ⊂ V .
Cosine similarity of a node i in two instances of the graph, G t and G t ′ at time t and t ′ , respectively, is defined as

|N t i N t ′ i | |N t i |×|N t ′ i |
where N t ′ i is the neighborhood set for node i at time t ′ .

Spectral Distance

Changes in the graphical structure is also computed using the difference in their Laplacian spectrum [START_REF] Pincombe | Detecting Changes in Time Series of Network Graphs using Minimum Mean Squared Error and Cumulative Summation[END_REF][START_REF] Jurman | An Introduction to Spectral Distances in Networks[END_REF]. Laplacian spectrum is defined through the eigen values of the Laplacian matrix. The distance between the eigen values of the Laplacian matrices corresponding to time t and t ′ is defined as the spectral distance between the two graphs corresponding to time t and t ′ . Let λ i be the i th eigen value of the Laplacian matrix of the graph at time t while µ i be the i th eigen value of the Laplacian matrix of the graph at time t ′ . The spectral distance is defined as

sd =                    |V | i=1 (λi-µi) 2 |V | i=1 (λi) 2 if |V | i=1 (λ i ) 2 ≥ |V | i=1 (µ i ) 2 , |V | i=1 (λi-µi) 2 |V | i=1 (µi) 2
otherwise.

(2.8.1)

For a system where no change has occurred, the eigen values of the two Laplacian matrices will be identical. This will result in sd = 0.

Rank Overlap

Stability can also be measured by computing rank overlap as suggested in [START_REF] Braha | From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks[END_REF][START_REF] Braha | Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interaction[END_REF]. For email network, Braha et al. [START_REF] Braha | From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks[END_REF][START_REF] Braha | Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interaction[END_REF] suggested to compute the degree of all nodes in the network at a given time instant. Once the degrees are computed, the nodes are ranked based on their degree. As the email networks are large, top x = 1000 nodes are selected from the ranking. This process is done for different time instants and respective lists are made. Commonalities between two selections are then found in the form of same nodes appearing in the two lists. Let G t T op and G t ′ T op be the lists of all top x nodes at time t and t ′ , respectively. Braha et al. in [START_REF] Hill | Dynamic Model of Time-Dependent Complex Networks[END_REF] defined the Rank Overlap as

S = G t T op G t ′ T op x .
(2.8.2)

Adjacency Matrix Based Measures

Stability of a link can be measured using changes in the adjacency matrix [START_REF] Hanneke | Discrete Temporal Models of Social Networks[END_REF][START_REF] Tang | Small-World Behavior in Time-Varying Graphs[END_REF]. Consider a graph,

G(V,
, (A t ) ij (A t ′ ) ij + (1 -(A t ) ij )(1 -(A t ′ ) ij ).
In another related study, Tang et al. [START_REF] Tang | Small-World Behavior in Time-Varying Graphs[END_REF] argued that the link with status 0 in both the instances should not be considered for the stability as the link did not exist in any of the considered time

instances. That is, (1 -(A t ) ij )(1 -(A t ′ ) ij
) term should not be considered.

Entropy

Zayani et al. [START_REF] Zayani | Improving Link Prediction in Intermittently Connected Wireless Networks by Considering Link and Proximity Stabilities[END_REF] showed that stability of a link can be computed using entropy measure. Consider a graph G t (V, E t ) with set of nodes V and set of edges E t at time instance t such that |V | ∈ N and |E| ∈ Z + . Let E t ij be the state of an edge between two nodes i ∈ V and j ∈ V at time t such that E t ij ∈ {0, 1}. Let Λ be the set of all the states of the edge between i and j over time

T . Thus Λ = {E 1 ij , • • • , E T ij }.
[99] calls Λ as a string of length T consisting of either 0 or 1. Note that |Λ| = T . Zayani et al. first extracted unique substrings from Λ. Let Λ x denote the x th element in Λ. For extraction of the set of unique substrings, W , the algorithm they applied is given in Algorithm 1.

Algorithm 1 W finding Let W ← ∅, Y ← {Λ 1 } for x f rom 1 to T do if Y ∈ W then if Λ x+1 = ∅ then Y ← {Y, Λ x+1 } end if else W ← W Y Y ← ∅ if {Λ x+1 } = ∅ then Y ← {Λ x+1 } end if end if end for
For example, consider Λ = {0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0}. Using Algorithm 1,

W = {{0}, {1}, {0, 0}, {0, 1}, {1, 0}, {1, 1}, {0, 0, 0}, {0, 0, 1}, {0, 1, 0}}. This will result in |W | = 9
where W consists of unique substrings extracted from Λ. Zayani et al. [START_REF] Zayani | Improving Link Prediction in Intermittently Connected Wireless Networks by Considering Link and Proximity Stabilities[END_REF] then defined entropy Ent ij of a link between nodes i and j as

Ent ij = |W | * ln(|W |) T . (2.8.3)
If the value of Ent ij is low the link is said to be stable however if not then it is said to unstable.

Note that a link,

E ij will have highest entropy if Λ = {0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, • • • }.
A link, E ij will have low entropy if Λ = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, • • • }. However, this method requires huge amount of memory as there is a need to store the history of the link. If the stability of each link in G is to be computed this method will require memory greater than O(|V | 2 T ) as there can be

|V |(|V |-1) 2
links in the graph. A similar entropy method is used in [START_REF] Song | Limits of Predictability in Human Mobility[END_REF] where location preferences are used instead of links to predict the human mobility.

Neighborhood Based

Let G t (V, E t ) be a graph with set of nodes V and set of edges E t at time t such that |V | ∈ N and

|E t | ∈ Z + .
Given two snapshots of this graph at t and t ′ a way to compute the stability of a node, i ∈ V , is through finding the intersection between the neighborhood nodes at time t and t ′ . Let N t i be the neighborhood of i ∈ V at time t and N t ′ i be the neighborhood of i ∈ V at time t ′ such that N t i ⊂ V and N t ′ i ⊂ V . The stability of node is defined as

S i =      |N t i N t ′ i | |N t i | if N t i = ∅, undefined if N t i = ∅.
(2.8.4)

The numerator of the case when N t i = ∅ in the eq. 2.8.4 refers to common links that existed both at t and t ′ . Let E t ij be the state of an edge from i ∈ V to j ∈ V -{i} at time t and E t ′ ij be the state of an edge from i ∈ V to j ∈ V -{i} at time t ′ . In terms of edges the numerator is expressed as

∀j∈N t i N t ′ i E t ij ∧ E t ′ ij
where ∧ denotes the logical AND operator.

Note that for N t i = ∅, S i is not defined. If N t ′ i = ∅ and N t i = ∅ then stability is 0. A similar method for computing node stability to that of eq. 2.8.4 is proposed in [START_REF] Brust | Heuristics on Link Stability in Ad Hoc Networks[END_REF][START_REF] Brust | Node Stability in Dynamic Communication Networks[END_REF].

However, the computation of the stability measure using the eq. 2.8.4, requires the knowledge of two snapshots of graphs in time, t and t ′ . This means, the node is first required to find its neighborhood at time t ′ and only then the computation of the stability can be performed. To reduce the time required for the algorithm to compute stability, it is beneficial if a node is able to predict the links before. This forms the basis of our proposed stability estimation method in Chapter 4.

Information Dissemination

Spreading models across population have always been in focus since its introduction in 1766 and various models have been proposed. Models related to spreading in the network have been well

studied. Most of these models are primarily inspired from epidemic spreading within the population that is divided into communities where the interaction between the communities is based on mobility [START_REF] Arino | Disease Spread in Metapopulation[END_REF][START_REF] Sattenspiel | A Structured Epidemic Model Incorporating Geographic Mobility among Regions[END_REF]. Epidemic spreading models are often studied in terms of reach in the population where reach is defined as the number of people under the influence of the epidemic. A node in the population is considered to be in either of the following states, Susceptible, Infected, Recovered and Exposed.

A node is said to be in state S if it is not infected by the disease but is likely to gain the disease in future. A node is said to be in state I when the node has the disease. State R corresponds to the recovered state of the node, meaning that a node was infected before but has now gained immunity, while the state E means that a node is exposed to the disease and is highly likely to gain infection.

The transition from one state to another occurs with a defined rate.

One of the main studies focusing on the spreading in the network is that of Watts and Strogatz's [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF] where they showed that, in static network, rewiring few links can reduce the AP L of the network.

The smaller the AP L, the smaller the number of hops between two nodes. This relates to the fact that less time is taken to spread the information in the network in terms of hops. We define the spreading of information as the information dissemination process in the network.

Information dissemination is not limited to static networks. It is also studied in dynamic networks. In dynamic scenarios, dynamicity affects the dissemination of the information in the network [START_REF] Kivelä | Multiscale Analysis of Spreading in a Large Communication Network[END_REF]. It is thus critical, while modeling dissemination, to know what application is targeted.

For example, the spread of a warning signal in the community should be very fast. However, the dissemination of viruses should be very slow. Dissemination is also affected by many other factors like, strength of the ties [START_REF] Miritello | Dynamical Strength of Social Ties in Information Spreading[END_REF], network structure [START_REF] Nicosia | Impact of Network Structure on a Model of Diffusion and Competitive Interaction[END_REF], activity pattern [START_REF] Vazquez | Impact of Non-Poissonian Activity Patterns on Spreading Processes[END_REF], content type [START_REF] Wang | Understanding the Spreading Patterns of Mobile Phone Viruses[END_REF],

node characteristics [START_REF] Wang | Information Spreading in Context[END_REF], altruism [START_REF] Hui | Selfishness, Altruism and Message Spreading in Mobile Social Networks[END_REF], etc.

In Communication networks such as Delay Tolerant Networks, information dissemination has been closely related to epidemics across the population where epidemic models like Susceptible-Infected-Susceptible (SIS) and Susceptible-Infected-Recovered (SIR) have been considered [START_REF] Valler | Epidemic Spread in Mobile Ad Hoc Networks: Determining the Tipping Point[END_REF][START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Maiti | Epidemic Broadcasting in DTNs using Directional Antenna[END_REF][START_REF] Maiti | Analyzing the Performance of Epidemic Broadcasting in DTNs using Directional Antenna[END_REF]. Information dissemination, however, has also been studied using rumor spreading or the gossip based algorithms [START_REF] Shah | Gossip Algorithms[END_REF][START_REF] Ko | Epidemic-Based Information Dissemination in Wireless Mobile Sensor Networks[END_REF].

We now describe our methods for enhancing information dissemination in the network. In Chapter 3, we use the concepts like small world, beamforming, Lateral Inhibition, analogy to flocking rules and non-uniform distribution primarily to build our algorithm. In Chapter 4, however, we use beamforming, human mobility model and stability concept. In Chapter 5, we use data from mobile Call Detail Records (CDR) to extract human mobility patterns. We also use beamforming to build our model. Note that all Chapters use beamforming and information dissemination concept.

CHAPTER3

Achieving Small World Properties in Wireless Network using Bio Inspired Techniques

Decades of academic and industrial research in wireless networks [START_REF] Akyildiz | Wireless Sensor and Actor Networks: Research Challenges[END_REF] has led to a tremendous growth of wireless networks requiring researchers to address manageability and scalability issues.

Due to these issues, most of the research work has been oriented towards autonomous wireless networks. The autonomous behavior of the wireless nodes made decentralized computing and cost efficient topology deployment possible [START_REF] Dressler | Self-Organization in Sensor and Actor Networks[END_REF]. It was also proved that self-organization of the network can lead to better performance.

An attractive model to achieve better network performance is the Small World network. Small world networks are characterized by reduced AP L and maintained CC. Drawing inspiration from the experimental work of Stanley Milgram [START_REF] Travers | An Experimental Study of the Small World Problem[END_REF], Watts et al. [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF] proposed a model that could achieve small world properties. In the model, Watts et al. proposed, small world properties could be reached by randomly rewiring a few existing links within the network. Watts et al. showed that the dynamics of these small world networks lie between that of a regular network and a random network [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF][START_REF] Watts | Small Worlds: The Dynamics of Networks between Order and Randomness[END_REF].

To prove the findings, however, Watts et al. used a regular wired network and called the rewired links as shortcuts. Many complex real world networks such as internet, biological networks, food web and social networks also demonstrate small world properties [START_REF] Newman | The Structure and Function of Complex Networks[END_REF][START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF][START_REF] Barabási | Scale-Free Networks[END_REF]. Section 2.2 provides more details on small world networks.

However, Watts' model cannot be applied directly to wireless ad hoc networks because of the spatial nature of such networks. In wireless ad hoc networks, addition of a shortcut between any two nodes should depend on the distance between two nodes. Helmy in [START_REF] Helmy | Small Worlds in Wireless Networks[END_REF] first studied the effect of adding few distance-limited links in the network. He showed that, upon introduction of distancelimited links, wireless ad hoc networks show small world properties. He concluded that, when the shortcut lengths are 1 4 th of the network diameter, there is a maximum reduction in the AP L. Thus, proving that realization of small world properties in a wireless ad hoc network depends crucially on the length of the shortcuts created. Another important factor in the realization of small world properties is the choice of nodes among which shortcuts are to be created. One method to obtain these nodes is that of preferential attachment [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF][START_REF] Simon | On a Class of Skew Distribution Functions[END_REF], typically observed in real world networks, wherein links are created to nodes with high structural importance. It was shown that, analogous to real world networks, using preferential attachment for creation of distance-limited links in a spatial network resulted in reduced network diameter [START_REF] Manna | Modulated Scale-Free Network in Euclidean Space[END_REF][START_REF] Barthélemy | Crossover from Scale-Free to Spatial Networks[END_REF]. This is accompanied by high clustering coefficient and a shift in the node degree distribution towards power law. These results motivate us to say that, creation of links to nodes having high structural importance in the network can result in the desired small world characteristics.

The creation of a wireless ad hoc network with the small world properties also depends on the manner in which distance-limited shortcuts are added. Such shortcuts can be added through different techniques like: (i) creating a directional beam using the same power as when the node is operating in the omnidirectional mode; (ii) increasing the omnidirectional transmission range of the node; (iii) introducing few long wired links [START_REF] Sharma | A Case for Hybrid Sensor Networks[END_REF]; (iv) introducing special nodes with higher omnidirectional transmission range deterministically in the network [START_REF] Guidoni | On the Design of Resilient Heterogeneous Wireless Sensor Networks Based on Small World Concepts[END_REF]; (v) using another antenna for beamforming in addition to the omnidirectional antenna.

Talking about the self-organization characteristics, [START_REF] Prehofer | Self-Organization in Communication Networks: Principles and Design Paradigms[END_REF], of the nodes, only techniques (i) and (ii) mentioned above qualify. However, even though other techniques help in achieving desired network characteristics, they lack self-organization capabilities. In addition, the second technique suffers from the problem of early death of the node due to increased energy consumption. Thus leaving only the first technique. Achieving reorganization or rewiring in a wireless ad hoc network through the first technique is hard due to the spatial nature of the wireless ad hoc network. Finding the beam direction, the beam length and determining the new neighborhood are the primary issues associated with rewiring in a wireless ad hoc network.

Most of the literature in this direction has been limited to the introduction of an external infras-tructure and considers global knowledge of the network. Acquiring such global information incurs additional overheads, thereby impacting the network performance. A related study, [START_REF] Banerjee | A Self-Organization Framework for Wireless Ad Hoc Networks as Small Worlds[END_REF], proves that the use of distance-limited long links in wireless ad hoc network to achieve small world properties is beneficial, (cf. Fig. 3.1). Let AP L(p) and CC(p) be the AP L and the CC of the network when p% of the nodes create long-range links. p = 0 means no node is beamforming. Fig. 3.1 shows a reduction in the AP L while almost no change in the CC for the case when a realistic antenna model (U LA antenna model) is used. On the other hand, for the theoretical model (sector antenna model 1 ), the reduction in the AP L is relatively less while the reduction in CC is considerably large.

The number of nodes that beamform is shown with a help of probability value in the log scale. The results also show that the reduction in the AP L increases with an increase in the number of beamforming nodes, [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF][START_REF] Watts | Small Worlds: The Dynamics of Networks between Order and Randomness[END_REF]. In fig. 3.1, we normalize AP L(p) with AP L(0) and CC(p) with CC(0) to account for the variation in the AP L and the CC. In [START_REF] Banerjee | A Self-Organization Framework for Wireless Ad Hoc Networks as Small Worlds[END_REF] it is also shown that fraction of asymmetric paths increases with the increase in the probability of rewiring for the U LA and the sector model (cf. Fig. 3.2). Definition 3.0.1. Consider two nodes i and j, an asymmetric path is a path when i is able to communicate with j while j is not able to communicate with i.

It is also noted that as the diameter of the network, D, increases, when beamforming is used using U LA and sector model, the AP L grows as O(log D) (cf. Fig. 3.3). Table 2.1 illustrats the comparisons between various studies performed with the objective of increasing connectivity using beamforming. We now formulate table 3.1 to illustrate comparisons and bring out the differences between various approaches in literature that focus on achieving small world characteristics in wireless networks and the proposed algorithm in this Chapter. There are various additional approaches other than those mentioned in the table, but they are not considered since they deal with external infrastructure of at least two radios.

In this Chapter, we investigate how increase in connectivity, reduction in the AP L and almost retention of the CC in a non-uniformly distributed wireless ad hoc network using only locally available information and beamforming can be achieved. Through the algorithm, we proposes to achieve the goals by creating long-range directional beams between nodes that have low and high structural importance. The decentralized computing and self-organizing requirements of such an approach motivates us to draw inspirations from nature and use natural phenomenon like Lateral Inhibition [START_REF] Lawrence | The Making of a Fly: The Genetics of Animal Design[END_REF][START_REF] Nagpal | An Algorithm for Group Formation in an Amorphous Computer[END_REF][START_REF] Nagpal | Engineering Amorphous Computing Systems[END_REF][START_REF] Afek | A Biological Solution to a Fundamental Distributed Computing Problem[END_REF] and Flocking [START_REF] Reynolds | Flocks, Herds and Schools: A Distributed Behavioral Model[END_REF]. In conjunction with these natural techniques, the concept of centrality also provides valuable insights in building a solution to the current problem.

We use Lateral Inhibition to create small logical regions within a static network. The use of Lateral Inhibition not only reduces the message complexity but also enables us to apply the Flocking rule analogy for beamforming successfully. We use the analogy of Flocking rules to identify the nodes that beamform and the beam properties. According to the rules, explained in Section 2.5 of Chapter 2, it is important to identify stray nodes, align the nodes and move them towards the centroid of their neighborhood. Analogous to this, after region formation in a non-uniformly distributed wireless ad hoc network, we use Flocking rules to identify the beamforming nodes and direct the beams of these beamforming nodes towards the centroid of the region. The centroid node in the region has a high structural importance. Beamforming towards the centroid node of the region contributes towards reducing the AP L because the centroid node of the region is the most connected node and has the highest Closeness Centrality measure. Thus, beamforming towards the centroid node is the preferential attachment behavior of the beamforming node, thereby making centroid finding a prerequisite to Flocking. Thus, we design the algorithm such that it first identifies regions using Lateral Inhibition, then identifies the centroid nodes of the regions and then uses the analogy of Flocking rules to identify the nodes that will beamform along with their beam properties.

The rest of the Chapter is organized as follows. Section 3.1 presents the assumptions used for the proposed algorithm along with the algorithm specifications. Section 3.2 presents the formal definitions. Sections 3.3 and 3.4 discuss the simulation setup and the results respectively while Section 3.5 provides concluding remarks. Further, table 3.2 lists the notations used in this Chapter.

g max maximum g G i (V i , E i ) region G i |G i ⊂ G
̺ ℘i peripheral neighbor of ℘ i |̺ ℘i ∈ P i ℘ i peripheral node |℘ i ∈ P i
Table 3.2: Notations and their meaning.

Assumptions and Algorithm

Assumptions

To address issues mentioned above, we focus towards the deployment of homogenous and autonomous wireless ad hoc nodes with no central entity controlling the nodes. This type of deployment enables us to easily apply self-organizing features, achieve global consensus with very limited local information, make any eligible node the group leader, make the system highly fault tolerant, ease the topological maintenance, lower the deployment cost and extend to incorporate the mobility of the nodes in the future. Let each nodes have an omnidirectional transmission range r such that r ∈ R + . We assume a non-uniform distribution of the nodes generated using thinning process defined by Bettstetter et al. [START_REF] Bettstetter | An Inhomogeneous Spatial Node Distribution and its Stochastic Properties[END_REF] (cf. Section 2.6) with parameters N min and r b such that N min ∈ Z + and r b ∈ R + in order to mimic realistic scenario. We assume the deployment of the nodes on a finite size 2-D plane of an area A.

As part of the network setup, we assume that each node has an antenna array consisting of M isotropic elements such that M ∈ N. Individually each AE has an omnidirectional radiation pattern.

The use of single antenna element, AE, results into omnidirectional beam while use of more than one AE results into a long-range directional beam. A node, however, decides to use more than one AE using simple local rules mentioned later in this section. A node uses beamforming only to transmit data but uses omnidirectional beams for reception. Consider the total transmission power available to nodes as p t such that p t ∈ R + . When a node decides to beamform using m ∈ [2, M ]

AEs out of M available AEs, each AE transmit with power pt m [START_REF] Bettstetter | How does Randomized Beamforming Improve the Connectivity of Ad Hoc Networks?[END_REF]. Note that when one AE is used, the AE transmits with full power p t and an omnidirectional beam is achieved. We use the theoretical antenna model, Sector model [START_REF] Yu | Connected Coverage in Wireless Networks with Directional Antennas[END_REF], and assume transmission of data to be synchronous.

As our objective is to demonstrate the improvements that is achieved in the network performance when beamforming is used over that of omnidirectional antenna, we assume a free space propagation model with path loss exponent α = 2.

Each node operates using local information, i.e., information available with one hop neighbors and itself. Determining single hop neighborhood to build the local information is thus essential for the correct operation of the algorithm. As our aim is to study the effect on the AP L and CC, we assume that the nodes have information about their neighborhood.

It is also essential to address the self-organizing paradigms, [START_REF] Prehofer | Self-Organization in Communication Networks: Principles and Design Paradigms[END_REF], to claim the self-organizing behavior of the network. The paradigms state: designing local rules to achieve global properties, implicit coordination, minimizing the use of historic information about the state of the network and designing an algorithm that changes with environment parameters. All nodes operate using only locally available information to determine whether they should beamform or not, decide beam properties and form regions. The nodes implicitly coordinate with their neighbors to determine the node with the highest hopcount from the centroid of the region. For a given region, the nodes also coordinate implicitly to determine the centroid node of that region.

In the following sections, we describe the system model and the algorithm.

System Model

Given a network, G(V, E), where V is the set of vertices such that |V | ∈ N and E is the set of edges such that |E| ∈ Z + , we visualize G as a network consisting of N r logical regions, {G 1 , G 2 , . . . , G Nr }, The set of vertices, V , is classified into three sets. These are termed as the peripheral node set (P ), the centroid node set (C) and the standard node set (S). Each set is provided with separate role. P contains the nodes that beamform. C contains the nodes towards which the nodes in the Peripheral node set beamform. The nodes in P and C are called as the peripheral nodes and the centroid nodes respectively. The nodes that are not in P or in C are said to be in set S. Note that

i.e., G = Nr i=1 G i such that 1 ≤ N r ≤ |V |. Each region, G i , consists of the set of nodes, V i such that V i ⊂ V where V = Nr i=1 V i ,
V = P + C + S.
Let hopcount ij be the distance in hops between nodes i and j, the closeness centrality of a node, i ∈ V , in a graph G is equal to We model directional beam using Sector model. A sector model is a simplified antenna model well suited for analysis purposes. In sector model, a beam is characterized by an area of a sector bounded between two radii of length B l each such that B l ∈ R + and an arc connecting the two radii. Note that the two radii have one common starting point which is also the location of the node. The length of the arc is obtained by the angle between the two radii. We call the angle as the width of the beam B w . Let the total transmission power available to the node be p t . As discussed above, when a node decides to beamform using m AEs out of M available AEs, each AE transmits with power pt m [START_REF] Bettstetter | How does Randomized Beamforming Improve the Connectivity of Ad Hoc Networks?[END_REF]. Note that when only one AE is used, the AE transmits with full power p t . We assume that in sector model, B l = r √ m. Further, as the overall p t is same, we assume the area under the omnidirectional beam and the sector are equal. This results into a sector where the B w is defined as

B w = 2πr 2 B 2 l . (3.1.1)

Algorithm

The algorithm presented here is divided into two parts:

A) Use of Lateral Inhibition technique and averaging scheme for the identification of regions and the centroid nodes of the regions, so that there are less message overheads and nodes can beamform towards the centroid node to achieve reduced AP L.

B) Use of Flocking rules to identify the nodes that beamform, to determine beam properties that realize small world properties and improve connectivity.

We describe these parts in detail in the next subsections.

Region formation

The Closeness Centrality [START_REF] Freeman | A Set of Measures of Centrality Based on Betweenness[END_REF][START_REF] Freeman | Centrality in Social Networks Conceptual Clarification[END_REF] identifies the structural importance of the node in the network.

The node with the highest Closeness Centrality value is the most central node in the network.

Through this node, the spread of the information to other nodes is fast. To determine the Closeness Centrality of the node, the node requires the knowledge of other nodes in the region as suggested by the definition of Closeness Centrality, Section 2.2.1. This makes the Closeness Centrality a global measure. Storing information about all the nodes in the network can consume a lot of node's memory. When there is a lack of global information, gathering such information can also be time consuming and the message complexity could be high. To overcome these problems, we create small logical regions. The creation of regions not only reduces the message complexity of the network but also reduces the effect on the AP L due to the failure of a node, thereby making the network more manageable, efficient and tolerant to failures [START_REF] Brust | LSWTC: A Local Small World Topology Control Algorithm for Backbone-Assisted Mobile Ad Hoc Networks[END_REF]. Some algorithms designed in this direction are centralized where the Base Station chooses the region heads based on the energy and the position of the nodes. Other techniques use either the transmission power of the node or the degree of the node [START_REF] Brust | WACA: A Hierarchical Weighted Clustering Algorithm Optimized for Mobile Hybrid Networks[END_REF]. On the contrary to centralized approaches, some algorithms are either distributed, [START_REF] Heinzelman | An Application-Specific Protocol Architecture for Wireless Micro-Sensor Networks[END_REF],

or probabilistic [START_REF] Younis | HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad Hoc Sensor Networks[END_REF].

Let us consider a node i ∈ V . As nodes lack global information, computing global centrality measure and using it will not be possible. Thus we use degree of a node as to build our algorithm.

For Lateral Inhibition, a node broadcasts and stores a message containing the following information:

the identity of the head node to which i is associated (h i ), its hopcount from h i and the degree of h i and the received hopcount is also the same, then the node updates the stored information using the lower h i . The node i then broadcasts the information it has after incrementing the hopcount by 1. Subsequently, i removes itself from H, i.e., H = H -{i}, and inhibits itself from acting as the regional head if the information was updated. Due to g and autonomous behavior, there is another check that has to be performed. It is possible that a node has an information about a head node that is no longer the head. In order to check for this condition, a node when inhibiting itself broadcasts a message saying that it is not an uninhibited node anymore. The nodes associated to this node thus reset their information and the process is again performed. The process continues until sufficiently large time T after which all nodes are either uninhibited or inhibited. We assume that each node knows this value of time. Each uninhibited node will thus have inhibited nodes associated to it forming a virtual region G i . All nodes in G i will be within g hops from the uninhibited node and will have same head node information.

(deg(h i ) = |N hi |,
We call the nodes having same head node to belong to one region, G i . Let V i be the set of nodes in G i . The nodes at different hopcount from the head node, h i , of the region G i virtually forms levels of different hops around h i , (cf. Fig. 3.4(d)). Note that a node with no neighborhood will be tagged as the head as it will uninhibited, (cf. Fig. 3.4(c)). However, the described technique does not guarantee that the head nodes identified above have a high Closeness Centrality value and are 2 4 6 8 10

(a) Uniform Node Distribution. To address this issue, the steps for the centroid node identification in a given region, G i , created using Lateral Inhibition are next described. As the centroid node is the most central node in the region, the coordinates of the centroid node can be approximated through averaging. Due to the lack of global information averaging is studied through reaching consensus over time.

Centroid Finding

Let the coordinates of the node j ∈ V i be (x j , y j ). Let the node have 2 copies of these coordinates.

One which is fixed and one which can be modified. Let the copy that can be modified be called as (x * j , y * j ). The nodes then communicate (x * j , y * j ) to their neighbors, N j,i ∈ V i . At the same time the node j receives such coordinate information from its neighbors in V i . Each node j ∈ V i then checks if the received coordinates are same as the stored one, (x * j , y * j ). If it is not same then using this information (the received coordinates of the neighbors and (x * j , y * j )), each node j ∈ V i computes an average of the coordinates and updates (x * j , y * j ). This updated information is then broadcasted to their neighbors in G i . When the process is run multiple times each node will have stored coordinates approximately same as those it receives from its neighbors. This process is continued until all nodes in G i have same average coordinates. This new average coordinate, (x * j , y * j ), approximates the coordinates of the centroid in G i . Note that the time taken to reach consensus can be large. However, in a G i with finite number of nodes, the consensus will be reached in finite time.

This technique reveals the location of the centroid node but not the identity of the node that is to be termed as centroid. In order to identify the centroid node of the region, nodes use their fixed copy of the coordinates and (x * j , y * j ) coordinates. Each node j checks if (x j , y j ) = (x * j , y * j ) ± ε, where ε is the error margin such that ε ∈ (0, r], and declares itself as the centroid. This process might result into multiple nodes declaring themselves as the centroid as two or more nodes can lie within the ε range of (x * j , y * j ). To avoid this, a node also considers their degree and egocentric betweenness. The nodes within ε range of (x * j , y * j ) share this information among themselves. Subsequently, the node having maximum sum of degree and egocentric betweenness declares itself as the centroid, c i of the region G i . Note that the above identification of centroid node is not valid for some topologies. For example, consider G i with 5 nodes having coordinates (r, r), (2r, 2r), (3r, 3r), (4r, 2r) and (5r, 1r) respectively. The coordinates of centroid node will be (3r, 9r 5 ). The above technique will result into no centroid node if ε = r. This problem will also occur in ring G i . Thus, to avoid such scenarios where no centroid node is identified we assume that the head node is the centroid node of the region.

After the identification of the centroid nodes, the centroid nodes broadcast their information in the network. All nodes then update their stored head information to their respective c i and the hopcount to their hopcount from c i .

Let the information about a centroid node be disseminated to nodes g max hop apart. We make g max > g. This dissemination of the centroid node information enables the nodes to build a set RC i which contains set of all centroid nodes within g max hops of the node i for future use. Algorithm 2 represents the algorithmic description of the region formation and algorithm 3 represents the centroid identification process. Fig. 3.4(e) shows the centroid nodes for the regions identified in Fig.

3.4(c).

Beamforming

According to the results of [START_REF] Helmy | Small Worlds in Wireless Networks[END_REF], it requires only a small fraction of nodes with long link capabilities to achieve small world properties. In a self organizing environment where all nodes possess beamforming capabilities, it is essential to identify nodes that create long-range beams along with the direction and the width of the beam. Flocking provides valuable insights in determining the answers to these questions. The nodes use insights from the Alignment rule of Flocking to identify themselves if they belong to the set P or not.

In our case the Alignment rule is the decision making of whether to beamform or not to beamform. However, we do not determine the new direction of the beam using alignment rule. The Alignment rule thus refers to the identification of the set of peripheral nodes, P i in the region G i . A node uses the hopcount of the neighborhood nodes to decide whether or not it is a peripheral node, ℘ i , in the region G i . If all nodes in the neighborhood, N j,i , of the node j in the region G i have hopcount less than or equal to the node's hopcount to the c i , then the node declares itself as a peripheral node.

The above statement means, for a given region G i with centroid c i , ℘ j ∈ P i ⇐⇒ hopcount ℘j ci ≥ hopcount N℘ j ci . A single unconnected node will always become a peripheral node because it does not have any neighborhood. Note that two peripheral nodes can be neighbors of each other due to the equality in the condition. When B l is small, i.e., when few AEs are used, the probability of connecting to the nodes in the original neighborhood is high as the beam is wider, (cf. Fig. 3.6(b)). However, when B l is long, i.e., when multiple AEs are used, the probability of connecting to the nodes in the original neighborhood is low as the beam is narrow, (cf. Fig. 3.6(c)).

As the number of sectors increases with an increase in the number of AEs, there is an increase in the time taken to decide the best sector. Checking all the sectors formed for all m ∈ [2, M ] requires a test of (M )(M +1) Non-uniformity reduces the size of the giant component in the wireless ad hoc network. In order to increase connectivity, it is thus important for the nodes to find different network components and connect them using beamforming.

set i Status ← U , i Head ← i, deg i ← |N i |, i hopcount ← 0, i coordinates ← (x i , y i ), B i = 0 7:
Initially broadcast(ID i , hopcount = 0, deg i ) until Time 30: end for In the proposed algorithm, similar analogy to address the connectivity issue is applied. In order to increase connectivity, nodes create beam in different directions from their peripheral neighbors.

if deg i < degree & hopcount < g then 13: i Status ← I, i Head ← ID, i hopcount ← hopcount + 1, deg i ← degree, B i ← 1 14: broadcast(recv, B i ) 15: else 16: if deg i == degree & i hopcount > hopcount & hopcount < g then 17: i Status ← I, i Head ← ID, i hopcount ← hopcount + 1, deg i ← degree, B i ← 1 18: broadcast(recv, B i ) 19: else 20: if deg i == degree & i hopcount == hopcount & hopcount < g & i Head > ID then 21: i Status ← I, i Head ← ID, i hopcount ← hopcount + 1, deg i ← degreeB i ← 1 22: broadcast(recv, B i )
In terms of Flocking separation rule, it is the decision to beamform in another direction. Consider

̺ ℘i ∈ P i as a peripheral neighbor of ℘ i then for all ̺ ℘i 's, ℘ i (B b ) = ̺ ℘i (B b ) must
hold where B b is the boresight direction. To make this decision, if ̺ ℘i of a ℘ i decides to create the beam in certain direction, ̺ ℘i informs ℘ i about the chosen direction before it actually creates the beam. ℘ i then tries to create the beam in another direction. ℘ i gives preference to connect to the nodes in other region rather than those of its own. This increases the possibility of connecting to an isolated region. Fig. 3.7 shows two nodes w and x which were initially neighbors of each other, create beams in different direction in order to increase connectivity.

Algorithm 3 Centroid finding

Let i be a region formed using region formation algorithm; for all j ∈ V i do

(x * j , y * j ) ← (x j , y j ) repeat Let f lag ← 0 for all k ∈ N j,i do recv k ← receive((x k , y k )) end for for all k ∈ N j,i do if recv k !=(x * j , y * j ) then set f lag ← 1 end if end for if f lag = 1 then for all k ∈ N j,i do (x * j , y * j ) ← (x * j , y * j ) + recv k end for (x * j , y * j ) ← (x * j , y * j )/|N j,i | broadcast((x * j , y * j )) end if until f lag = 1 end for Let X ← {} for all j ∈ V i ∈ V |(x j , y j ) -ε < j(x * , y * ) < (x j , y j ) + ε do X ← X + {j} compute sum j ← sum(|N j |, EBC j ) end for if X == {} then C ← C + {h i } else for all j ∈ X do c i ← j|j = max{sum j } C ← C + {j} end for end if for all k ∈ V do formulate RC k end for
Nevertheless, the choice of best direction of the beam and the knowledge of whether a ℘ i has a node within its 1 hop is still not provided. These problems are addressed next in this section.

To the above-mentioned problem, the analogy of Cohesion rule of Flocking to determine the best direction of the beam is used.

We apply similar analogy to cohesion rule in the proposed algorithm. We state that the cohesion rule is the decision to bind a peripheral node with a centroid node. From the previous Chapter, it can be noted that the centroid node has the highest Closeness Centrality value in a given region. As the AP L is the sum all shortest distances, any reduction in this summation will lead to a reduced AP L. In order to have maximum reduction in the path length, the node should connect to the farthest centroid. Directing the peripheral node's beam towards the centroid node will thus help reduce the average distance of the peripheral node to other nodes of the region in which the centroid node lies.

If the centroid node chosen by the peripheral node and the peripheral node itself were not initially connected, connecting them will help in increasing the connectivity, (cf. Fig. 3.7 where two peripheral nodes w and x which were initially neighbors of each other, create beams in different directions. In order to have increased connectivity, the node w creates a beam towards the region containing the centroid node y, while the node x creates a beam towards the region containing the centroid node z. Here g = 4.). On the other hand, if the centroid node chosen by the peripheral node and the peripheral node were connected and were some finite hops apart, beamforming will lead to the reduction in the AP L.

To account for choosing the correct centroid to connect, the peripheral node, ℘ i , builds RC * ℘i , a set of all centroid nodes reachable when it is beamforming. To determine RC * ℘i , the peripheral nodes sweep through all the sectors (m) created with the chosen number of AEs except the sectors in which

̺ ℘i 's have created the beam. If RC * ℘i -RC ℘i = ∅ and |RC * ℘i -RC ℘i | > 1, i.e.
, ℘ i identified two or more potential centroid nodes, assuming the hopcount to these centroid nodes as ∞ the decision to connect to one of them is randomly made. However, if RC * ℘i -RC ℘i = ∅, i.e., no new centroid is found, the ℘ i decides to connect to farthest centroid node in RC ℘i . However, this decision also depends on the hopcount between c i and ℘ i . Creating the beam toward the centroid that is less than two hops away will only reduce the initial neighborhood but not the AP L. In this case ℘ i drops the decision of being the peripheral node and remains omnidirectional. depicts the same. In fig. 3.8(a), node x is 5 hops away from y while it is 3 hops away from z and 2 hops away from the centroid of the region in which x lies. Thus, in order to have a reduced path length, node x decides to create beam towards y. On the contrary, in the case when the node x does not have the previously stored information about the centroid nodes y and z, the node considers hopcount to these centroid nodes as ∞ and randomly chooses one of them to connect to, (cf. Fig.

3.8(b)).

Whenever a peripheral node creates a beam towards a centroid node that is more than 1 hop away, asymmetric link may arise. This is due to the fact that the B l of peripheral node is r × √ m while B l of a centroid node is r, in other words, B l of Centoid B l of peripheral = 1 √ m . Due to this difference, peripheral nodes will not know if they got connected to the centroid of other region or not. We propose to solve this issue by performing following steps, when a centroid node receives information about the node trying to connect to it, it just for one time instant, to acknowledge the reception, creates the beam back to the node. This can be easily done after determining angle of incidence of the beam. This works well for both connected and unconnected components. Algorithm 4 represents a brief algorithmic description of beamforming using Flocking rule analogy. Fig. 3.9 shows the new network created as the output of the algorithm on the network shown in fig. 3.4(b). Fig. 3.9 uses g = 5 to create regions. In fig. 3.9 nodes marked in green beamform. Their directional beams are also shown in green. The nodes marked with black triangle do not beamform and the nodes marked with red square are the centroid nodes.

Definitions and Lemmas

Definition 3.2.1. Assume a centroid c i of the region G i , and a node j in V i which has the highest Closeness Centrality, then

j = arg max ∀k∈Vi {CLC k } CLC ci ≃ CLC j (3.2.1)
Definition 3.2.2. The node j with neighborhood N j,i of the region G i with centroid c i is a peripheral node ⇐⇒ hopcount jci ≥ hopcount Nj,ici .

Lemma 3.2.1. Let ρ be the initial node density in a given area A, r b be the radius chosen for the thinning process, N min be the minimum number of neighbors required and Γ(N min , ρr 2 b π) be (a) One component with three regions when g = 3. Here, the node x can create the beam towards y or z, but because the hopcount to y is more than z, node x creates the beam towards y.

(b) Three unconnected components with three regions when g = 4. Here, the node x can create the beam either towards y or z, but because the hopcount to y and z is same as ∞, x randomly decides between y and z to connect to. the incomplete gamma function. The expected number of nodes remaining, n, after applying the thinning processes, [START_REF] Bettstetter | An Inhomogeneous Spatial Node Distribution and its Stochastic Properties[END_REF], on a uniformly distributed network is defined by

E(n) = ρA 1 - Γ(N min , ρr 2 b π) (N min -1)! . (3.2.2)
Lemma 3.2.2. The separation between any two head nodes is between (g, 2g + 1] where g is the hopcount used to create the region, [START_REF] Nagpal | Engineering Amorphous Computing Systems[END_REF].

Proof. Consider a head node with all nodes within g hops around itself in its region. A node which is more than g hops away will lie in another region. If in the neighboring region, a head node does not have any region of its own around it, then the distance between the two head nodes in hops will be g + 1. On the other hand, if the neighboring region also has a region of size g around it, then the distance between two head nodes in hops will be 2g + 1.

Lemma θ ← Sector containing beamtonode 32: end for that are termed as centroid nodes, the nodes randomly decide for being the centroid and thus only one node is chosen as centroid. The value of ε is thus an important factor in the estimation of the centroid node. Also, smaller ε will tend to provide better estimation of the centroid nodes. As there is only one centroid node per region, the number of centroid nodes is equal to the number of regions. However, if no centroid is identified through the algorithm then the head node is termed as centroid node.

Lemma 3.2.4. If a node is not a centroid node, it is connected to a centroid node.

Proof. The algorithm identifies regions and their centroid nodes. An identified region is always connected, i.e., all the nodes in the identified region are connected to each other and there is one and only one centroid node in a region, lemma 3.2.3. Thus for a given region, all nodes that are not centroid are connected to the centroid node. Lemma 3.2.5. An unconnected node is both the centroid node as well as the peripheral node.

Proof. A single unconnected node does not have any neighborhood. It thus remains uninhibited at the end of the region formation phase and becomes the head. As it is lacking any neighborhood, the node does not have any other node in the region around itself and is the only node in the region.

In this region, the average coordinates perfectly match the average coordinates of the node. Thus it requires no further computation for correctly identifying the centroid node. This node is also the peripheral node as the condition of definition 3.2.2 holds true because of the unavailability of the neighborhood. Proof. From lemma 3.2.2, the hop distance between two heads is bounded by (g, 2g + 1].

Lower Bound : When the heads are separated by 2g + 1 hops, the number of regions formed are less. The number of nodes in one region is ρg 2 r 2 π. Thus, the total number of nodes in all the

N regions is |N |ρg 2 r 2 π. As the total number of nodes are |V |, ∴ |N | = |V | ρg 2 r 2 π . From lemma 3.2.3, |C| = |N |, ∴ |C| = |V | ρg 2 r 2 π
Upper Bound : When all the heads are separated by g + 1 hops, the number of regions formed are more. A head in such a case is connected to only 6 other heads. This can be visualized as a hexagon with vertex-vertex distance equal to g + 1 and a node at the center of hexagon. Each of the vertex nodes are shared between 3 other hexagons. Thus, the total number of heads that are exclusive for the hexagon are 6 3 +1 = 3. In other words, there are 3 heads in an area of 6g 2 r 2 √ Proof. From lemma 3.2.2, the hop distance between two heads is bounded by (g, 2g + 1].

Lower Bound : Consider k th component of the network. When the heads are separated by 2g+1 hops, the number of regions formed is less. The number of nodes in one region is ρ k g 2 r 2 π. Thus, the total number of nodes in all the regions in the component is N k ρ k g 2 r 2 π, where N k are the number of region in k th component. But as the total number of nodes were assumed to be

|V j k |, ∴ N k = |V j k | ρ k g 2 r 2 π .
Thus for all the components, the number of regions formed is

|N | = j k=1 N i = j k=1 |V j k | ρ k g 2 r 2 π . From lemma 3.2.3, |C| = |N |, ∴ |C| = j k=1 |V j k | ρ k g 2 r 2 π
Upper Bound : Upper bound to the number of regions arises when all nodes in the network are disconnected. Thus, all nodes in such a case will be uninhibited thereby becoming region heads.

Thus |C| = |V |.
Lemma 3.2.8. For a node distribution and fully connected network, and using lemma 3.2.6, the number of peripheral nodes in the network is bounded by |V |(2g-1)

g 2 and |V |(2g-1)π g 2 √ 3
.

Proof. Peripheral nodes are the nodes lying in the outer most part of the region. Thus, the number of nodes g hops away from head node of a region = ρg 2 r 2 πρ(g -1) 2 r 2 π = ρ(2g -1)r 2 π Now using lemma 3.2.6, the number of peripheral nodes for all regions thus varies between

|V |(2g-1) g 2
and |V |(2g-1)π

g 2 √ 3
.

Lemma 3.2.9. For a node distribution and network with j components (j > 1), and using lemma 3.2.7 and lemma 3.2.5, the number of peripheral nodes in the network is bounded by

j k=1 |V j k |(2g -1) g 2 and |V |.
Proof. Peripheral nodes are the nodes lying in the outer most part of the region. Thus, the number of nodes g hops away from head node of a region in

k th component = ρ k g 2 r 2 π -ρ k (g -1) 2 r 2 π = ρ k (2g -1)r 2 π.

Simulation Setup

We consider a simulation area of A = 500x500 to simulate the algorithm. r b and N min are set to 30 and 5 respectively to achieve the non-uniform distribution of node throughout the simulation area.

The non-uniform node distribution enables us to represent the real world scenarios. Initially, each node operates in omnidirectional mode using m = 1 AE with the omnidirectional radius as r = 30.

The maximum number of AEs that the nodes are equipped is set to M = 6. The separation between two AEs computed using W iF i frequency, f = 2.4Ghz.

Using such setting we first simulate the variation of percentage number of nodes in the giant connected component (GCC) for non uniform deployment for various average node densities, ρ, in the region. The simulation reveals that the percentage number of nodes in GCC ∈ (0.1, 0.9) for the range of ρ ∈ [1x10 -3 , 2.5x10 -3 ] (cf. Fig. 3.10). This is an ideal range for us to test our algorithm as we are interested in a disconnected network. Further, as non uniform deployment strategy is applied, nodes can become disconnected. This leads to a network that is less connected than the uniformly deployed network. However, when the density increases the size of the GCC also increases.

Further, through simulations, we explore the effect on connectivity, AP L and CC by varying the node densities and the region size. We use MATLAB to simulate the algorithm with a confidence interval of 95%. We average all the results over 50 topologies and set ε = 0.66r.

Results

First, we prove the correctness of the centroid finding in the region. For this, we compute the nodes that also have high Socio-Centric Betweenness is between 50% and 60% for g ∈ [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF][START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF]. Further, all the centroid nodes in the network are within hopcount < g. Fig. 3.11, however, also shows that for any g ∈ [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF][START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF], more than 95% of the time the centroid node is within 4 hops from the maximum Socio-Centric Betweenness value node.

We use g ∈ [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF][START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF] and Sector model to obtain the results, (cf. Fig. 3.12). Fig. 3.12(a) shows the effect of beamforming on the AP L. Note that the AP L is calculated for the largest component in the network. The AP L obtained in omnidirectional case is initially less than that obtained for the directional cases because the density of the nodes in the component is low. When the algorithm induces directional beams, due to the inclusion of the nodes in other network components, there is an increase in the AP L. The AP L for the directional case is less than that of the omnidirectional case when ρ > 2 * 10 -3 due to the fact that the nodes connect to the centroid node of other regions in the different component as well as in the same component. The region size affects the AP L. The lower the value of the region size, higher is the number of nodes that beamform, (cf. Fig. 3.12(e)), leading to more shortcuts and in turn more reduction in the AP L. For ρ = 2.5 * 10 -3 and g = 10, there is a reduction of almost 40% in the AP L while there is a reduction of almost 55% for g = 3, (cf. Fig. 3.12(f)). However, for ρ = 1 * 10 -3 and g ∈ [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF][START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF] when most nodes are unconnected, there is an increase of 70% in AP L due to the above-mentioned facts.

The introduction of the long-range beams also causes the CC to change, (cf. Fig. 3.12(b)). For very low-density networks, the CC for the directional case is less because beamforming leads to loss in the initial neighborhood. However, for higher density networks, the CC does not vary as much as the AP L (cf. Fig. 3.12(f)). For ρ = 2.5 * 10 -3 , there is a reduction of 25% and 38% for g = 10 and g = 3 respectively. However, for ρ = 1 * 10 -3 and any g ∈ [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF][START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF], the reduction in CC is almost 40%.

The number of components in the network can define connectivity. In a very low-density omnidirectional network, the number of disconnected components is higher, (cf. Fig. 3.12(c)). The number of disconnected components increases to a certain maximum and then decreases as the density increases. This is because, for a high density, all nodes can find at least one neighborhood node within their reach. In addition, as the number of components decreases, the connectivity increases.

For the directional case however, as nodes beamform towards different components with the ob- (a) Average path length in hops. jective of increasing connectivity, the number of disconnected components is less than that of the omnidirectional case.

The size of the giant component can also explain the connectivity of the network. For the directed graphs however, [START_REF] Dorogovtsev | Giant Strongly Connected Component of Directed Networks[END_REF] defined the giant component using the Giant Strongly Connected Component (GSCC) 3 and the Giant In-Component (GIN ) 4 . Thus, we calculate the size of GSCC and GIN .

We show the difference between the size of the giant component for omnidirectional network, GSCC and GIN . As stated in [START_REF] Dorogovtsev | Giant Strongly Connected Component of Directed Networks[END_REF] that GSCC ⊂ GIN , we also observe that GIN is a bigger set and contains more nodes than GSCC. The percentage of number of nodes in GIN reaches 1 very early, The number of centroid nodes (|C|) depends on the value of the region size, (cf. Fig. 3.12(d)). For a low-density network, the value of the region size does not matter, while as the density increases the value of the region size affects the number of regions formed. As the region size increases, more nodes are inhibited leading to less number of regions. The difference between the number of regions formed for g = 3 and g = 10 is of 40 for ρ = 2.5 * 10 -3 while the difference for ρ = 1 * 10 -3 is very less.

The value of the region size used also affects the number of peripheral nodes (|P |) identified, (cf. Fig. 3.12(e)). For a low value of region size, as there are more regions, more nodes are included in P because of the reduced neighborhood with respect to the region. However, when the value of the region size is large, |P | is less because there are more nodes in the region and the nodes have relatively more neighbors to check before making the decision of beamforming. |P | greatly affects the number of unidirectional paths. However, it has an adverse effect on the CC. As the number of peripheral nodes increases, unidirectional paths between the nodes also increases leading to more loss in the CC. For ρ = 1 * 10 -3 and g ∈ [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF][START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF], the difference between the number of peripheral nodes is almost negligible. For ρ = 2.5 * 10 -3 , however, the number of peripheral nodes varies by more than 120 as the regions formed for lower region size are more.

The algorithm affects the AP L and the CC of the network when U LA model is used, (cf. Fig. (a) Average path length in hops.

Conclusion

In this Chapter, we present an algorithm for achieving small world properties using beamforming and bio-inspired techniques in a wireless ad hoc network. The algorithm uses locally available information and does not require the global knowledge of the network. The algorithm operates in decentralized environment where the nodes do not require any external infrastructure to achieve the goals. We also show that isolated communities can be connected using beamforming with each other to achieve more dissemination of information. In the algorithm, bio-Inspired techniques like Lateral Inhibition and Flocking are used to form virtual communities within the network for the reduced message complexity and to determine beam properties respectively. Through the results it is also shown that for both theoretical and realistic antenna models and relatively high-density networks, there is a reduction in the AP L by almost 40% to 68% for g ∈ [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF][START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF]. On the other hand, reduction in the CC is between 19% to 38%. The results also show improvements in the connectivity. Through the use of the algorithm we show that the increase in the size of the GSCC for the non-uniformly distributed directional network is around 10% for high density network while it is around 61% for relatively low density networks. intermittent and change with time. In such networks, connectivity of the network changes every ∆t instant, due to the changes in the network structure. This results into time varying path length between two devices and hence affects the flow of information from one device to another [START_REF] Kim | Temporal Node Centrality in Complex Networks[END_REF].

The properties of time varying graphs are well studied using discrete time snapshots of the network [START_REF] Kim | Temporal Node Centrality in Complex Networks[END_REF][START_REF] Birand | Dynamic Graph Properties of Mobile Networks under Levy Walk Mobility[END_REF]. Other than mobility, other factors studied in literature that affect the dissemination process in the network are, bursty data [START_REF] Karsai | Small but Slow World: How Network Topology and Burstiness Slow Down Spreading[END_REF], strength of the connection [START_REF] Miritello | Dynamical Strength of Social Ties in Information Spreading[END_REF], network structure [START_REF] Nicosia | Impact of Network Structure on a Model of Diffusion and Competitive Interaction[END_REF],

activity pattern [START_REF] Vazquez | Impact of Non-Poissonian Activity Patterns on Spreading Processes[END_REF], content type [START_REF] Wang | Understanding the Spreading Patterns of Mobile Phone Viruses[END_REF], node characteristics [START_REF] Wang | Information Spreading in Context[END_REF] and altruism [START_REF] Hui | Selfishness, Altruism and Message Spreading in Mobile Social Networks[END_REF]. Note that time varying are also termed as Evolving Network [START_REF] Schwarzkopf | Epidemic Spreading in Evolving Networks[END_REF][START_REF] Borgnat | Evolving Networks[END_REF], Evolving Graphs [START_REF] Grindrod | Evolving Graphs: Dynamical Models, Inverse Problems and Propagation[END_REF][START_REF] Grindrod | Communicability across Evolving Networks[END_REF][START_REF] Grindrod | Social Networks: Evolving Graphs with Memory Dependent Edges[END_REF], Adaptive Network [START_REF] Braha | From Centrality to Temporary Fame: Dynamic Centrality in Complex Networks[END_REF][START_REF] Braha | Time-Dependent Complex Networks: Dynamic Centrality, Dynamic Motifs, and Cycles of Social Interaction[END_REF], Dynamic Networks [START_REF] Kuhn | Dynamic networks: Models and Algorithms[END_REF] and Temporal Networks [START_REF] Holme | Temporal Networks[END_REF][START_REF] Pan | Path Lengths, Correlations, and Centrality in Temporal Networks[END_REF].

In [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Maiti | Epidemic Broadcasting in DTNs using Directional Antenna[END_REF][START_REF] Maiti | Analyzing the Performance of Epidemic Broadcasting in DTNs using Directional Antenna[END_REF] it is shown that when beamforming is combined with mobility, much faster information dissemination is achieved in terms of broadcasting time. The broadcasting time is defined as the time at which all devices have received the information. These studies also prove that (i) only a small fraction of devices are needed to beamform for enhancing the information dissemination process in the mobile network and (ii) better performance in terms of information dissemination is achieved when the beams are longer, narrower, use same power as that of omnidirectional beam and when the antenna rotates while the devices move. Another work related to beamforming in the mobile communication networks is by Li et al. [START_REF] Li | Collaborative Vehicular Content Dissemination with Directional Antennas[END_REF]. The study by Li et al. [START_REF] Li | Collaborative Vehicular Content Dissemination with Directional Antennas[END_REF] focuses on the effect of beamforming in a human centric vehicular network. Li et al. show that beamforming can enhance information dissemination process in a mobile network with similar observations as that of [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Maiti | Epidemic Broadcasting in DTNs using Directional Antenna[END_REF][START_REF] Maiti | Analyzing the Performance of Epidemic Broadcasting in DTNs using Directional Antenna[END_REF]. However, the only difference between [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Maiti | Epidemic Broadcasting in DTNs using Directional Antenna[END_REF][START_REF] Maiti | Analyzing the Performance of Epidemic Broadcasting in DTNs using Directional Antenna[END_REF] and [START_REF] Li | Collaborative Vehicular Content Dissemination with Directional Antennas[END_REF] studies is in the selection of the devices that beamform. However, in these studies only single source information dissemination scenario was considered. Contrary to [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Maiti | Epidemic Broadcasting in DTNs using Directional Antenna[END_REF][START_REF] Maiti | Analyzing the Performance of Epidemic Broadcasting in DTNs using Directional Antenna[END_REF], where the direction of the beam and the choice of the beamforming devices was random, we believe that, if the selection of the devices that beamform is made based on a measure and the beams are directed in a direction where there are more devices that do not have the information, the dissemination process can be enhanced. That is, if preferential attachment features are incorporated in mobile networks information dissemination process can be enhanced.

Determining which device should beamform is surely the first question that has to be answered in this context. After finding the beamforming devices, the direction of the beams has to be determined.

In Chapter 3, we proposed the use of centrality measure with other concepts to solve the problem in a static network. In Chapter 3, the preferential attachment feature was incorporated as the preference to attach to the devices that has the highest closeness centrality. As discussed in Chapter 3, the computation of closeness centrality requires global network knowledge. In an autonomous environment where devices lack global knowledge the computation of centrality measure is time consuming. In mobile environment, where the position of the devices change frequently, it is hard to directly apply steps in Chapter 3 as it will be a slow process (the device can move by the time the highest closeness centrality device is found). Other methods for computing closeness centrality in dynamic conditions will be computationally expensive, complex, energy wasteful and will require historical information [START_REF] Kim | Temporal Node Centrality in Complex Networks[END_REF][START_REF] Kim | Centrality Prediction in Dynamic Human Contact Networks[END_REF]. Storing huge amount of historic information in a memory limited device could raise computational issues.

In the context of multi-packet dissemination and mobile networks, we are particularly interested in the measure of stability in networks. A key distinguishing feature of the approach taken here is that low stability is accompanied by diversity in content and can therefore be a catalyst for information dissemination. Stability is the complement of the change in the system. One way of defining Stability is using the fraction of neighborhood devices kept intact. Let S be a measure that quantifies stability of a device and let it be given by the eq. 2.8.4 as defined in Section 2.8.6.

Let us assume discrete time steps where devices are able to jump from one location to another. This definition results into S ∈ [0, 1] + {undef ined}. Note that S = 1 implies (i) the device is still connected to all of its neighbors at time t and no new device has become its neighbor and (ii) the device is still connected to all of its neighbors at time t and new neighbors have joined. In the first case the device will be limited to the information flowing within its neighbors at time t as no new device has joined the neighborhood set.

If S = 0, it implies (i) the device has lost all of its neighbors at time t completely and no new neighbor has joined and (ii) the device has lost all of its neighbors at time t and new neighbors joined it. Here, in the second case it will mean that the device has met more devices over time and will have the information flowing among neighbors at time t, while being able to receive the information flowing among new neighbors at time t + ∆t. In the case of different types of information flowing in the network, this gives more diversity to the device in terms of knowledge about different types of information flowing in the network. However, 0 < S < 1 implies (i) the device has maintained some of its neighbors at time t and no new neighbor has joined and (ii) the device has maintained some of its neighbors at time t and new neighbors have joined. Further, S = undef ined means that the device had no neighbors at time t and thus would have not received any information flowing in the network at time t.

However, the stability measure proposed in Section 2.8.6 requires two network snapshots. One initial and one at the time when the stability measure has to be computed. In a mobile scenario where beamforming is also applied, before the information can be transmitted using stability as defined in Section 2.8.6, it requires following steps: (i) identification of the new neighborhood at time t + ∆t; (ii) the computation of stability as defined in Section 2.8.6; (iii) beamforming and (iv) finding new neighborhood under beamforming. Performing these steps will consume time, energy and will stall the dissemination until the above steps are performed. Thus, it is beneficial for a device if it can estimate its stability before performing step "(i)" (knowing its neighbors at t + ∆t) using its neighborhood at t only and mobility characteristics.

In order to determine which devices should beamform, we use the stability measure and proposes which devices should beamform and in which direction. One straight forward choice for the beamforming devices are the devices with low stability. This choice relates to the fact that when different types of information are flowing in the network, low stability devices are likely to have large diversity of information. If such devices beamform they will be able to transmit more information to far away devices. Alternatively, one intuitive choice of devices that can serve the purpose of preferential attachment are the devices with high stability. High stability devices are likely to be limited to the information flows within limited set of neighbors. Connecting to them will make them aware of more information flowing in network and will help them gain all the information flowing in the network more quickly. Thus, in this Chapter, we use the above mentioned discussion to build our algorithm.

We focus on how information dissemination can be further enhanced in a dynamic spatial network where devices lack global knowledge about the network and have limited memory. Towards this, we first show how devices can predict their stability and use it to identify if they should beamform and where the beams should be directed. More explanation is provided in Section 4.1.

Algorithm

In this Section we provide a method to estimate the stability of the node in the dynamic environment and how this stability can be used toward enhancing the information dissemination process in a mobile network. We first list assumptions used to build the algorithm and then propose the algorithm.

Assumptions

Let, initially at time t = 0, |V | autonomous devices be distributed in a square area A, where V is the set of autonomous devices such that |V | ∈ N and A ∈ R 2 . In graph terminology, these devices are the nodes in the graph. Here, we consider V to be fixed. Let, each device in V have a transmission radius r such that r > A |V |π . We assume that the probability of connection in all the directions is 1, i.e., we consider a disk model with radius r. Note that choosing such r ensures the existence of a giant connected component (GCC) where number of devices in GCC are greater than 1 [START_REF] Németh | Giant Clusters in Random Ad Hoc Networks[END_REF][START_REF] Bettstetter | On the Connectivity of Ad Hoc Networks[END_REF].

Consider a device i ∈ V , for all devices in V -{i} that have Euclidian distances less than or equal to r with i are considered to be connected to i and in the neighborhood of i. Let all the devices in V possess only local knowledge (knowledge limited to one hop neighborhood) and lack global knowledge of the network like, number of devices in the network and the location of all the devices. Let each device be memory limited. Consider, at time t, a device i possess the following information: its own location coordinates and two threshold measures, maximum stability threshold, S max , and minimum stability threshold, S min such that 0 < S max < 1 and 0 < S min < 1. Further, we assume that each device is equipped with an antenna array consisting of maximum M antenna elements (AE) arranged in a linear manner as in the U LA antenna model where, individually, each AE has an omnidirectional radiation pattern. An omnidirectional beam, is achieved using single AE, m = 1, while a long range beam is achieved when m ∈ [2, M ]. As we are interested in the dissemination process and the benefit achieved while beamforming, we set the path loss exponent to 2 and assume free space propagation. Further, in this Chapter, we assume directional transmission and consider omnidirectional reception. Let x min be the minimum jump length such that x min ∈ R + and x min > 0. Let the direction of the jump be uniformly chosen from [0, 2π]. As discussed in Section 2.7, the jump length of human mobility follows truncated power law distribution. We use this fact to state that the distribution of the jump lengths is known. Thus, we assume that x min , α and β used in the eq. 2.7.1 are known where α > 0 and β ≥ x min . Following this we assume that the jump lengths are sampled from the truncated power law distribution (cf. eq. 2.7.1). Let the devices be carried by humans. This will mean that a jump made by a device also mimic jumps made by humans. We assume that these jumps are made in discrete time, i.e., a jump is made by a device i ∈ V from a given location in ∆t > 0 time causing changes in the graphical structure. Let after the jump, at time t + ∆t, the device i possess information about its location at time t, its location at time t + ∆t, and the acquired location coordinates of the devices in N t i . After the devices have moved, each device estimates its stability for the time instant t + ∆t based on the neighborhood at t. Further, we assume that the network operates in synchronous mode.

Stability Estimation

As terms nodes and devices can be used interchangeably, in the current Section we use the term node to represent a device. We now propose a method to estimate the stability measure. Let i t denote the coordinates of the location of node i at time t. Let i t+∆t denote the coordinates of location of node i at time t + ∆t. Following the assumptions discussed above, let the distance traveled by a node i ∈ V in time ∆t be b i such that b i ≥ x min . Let N t i be the set of neighbors of node i at time t. Let the distance between the location of a neighbor j (j ∈ N t i ) at time t, j t , and that of node i at time t + ∆t, i t+∆t , be l j such that l j ≥ 0. l j = 0 relate to the fact that the node i has moved to the location j t . Let the distance traveled by the neighbor j in ∆t time be a j such that a j ≥ x min .

In order to estimate the stability, it is essential to know if node j is connected to node i at time t + ∆t. Let C be the event that node i is connected to node j at t + ∆t. To calculate the probability of event C, P i,j (C), one requires the knowledge of l j , r and a j . Note that node i does have the knowledge of l j and r. However, node i does not know the exact displacement of node j; it has only distributional knowledge of a j . The distribution of a j follows human mobility pattern and is given by the truncated power law distribution (cf. eq. 2.7.1 in Section 2.7).

Suppose that node i knows the exact value of a j . We calculate the probability of event C given a j denoted by P i,j (C|a j ). Consider a circle C 1 of radius a j centered at j t . Note that the new position of node j at time t lies on C 1 . Consider another circle C 2 of radius r centered at i t+∆t . Let D 1 and D 2 denote the circular disk areas covered by C 1 and C 2 respectively. Note that D 2 is the area in which if a node j, j = i, lies, then it is connected to node i at time t + ∆t, because D 2 is the transmission area of node i. For the nodes i and j to be connected with a positive probability, node j must lie in D 2 at time t + ∆t, i.e., D 2 must have nonempty intersection with C 1 .

First, we would like to determine the conditions when we can conclude with certainty that the two nodes i and j are connected or disconnected, i.e., when P i,j (C|a j ) = 1 or P i,j (C|a j ) = 0. If D 2 completely encapsulates C 1 , then P i,j (C|a j ) = 1. If the intersection of D 2 and C 1 is empty, then P i,j (C|a j ) = 0. In all other cases, 0 < P i,j (C|a j ) < 1. Fig. 4.1(a) depicts the scenario when D 2 encapsulates C 1 . This corresponds to the situation when the transmission radius r is large enough so that all possible locations of node j fall within the transmission area of node i at time t + ∆t. In this case, we have P i,j (C|a j ) = 1.

However, if C 1 encapsulates D 2 then P i,j (C|a j ) = 0 (cf. Fig. 4.1(c)). Further, if D 1 D 2 is empty, then P i,j (C|a j ) = 0 (cf. Fig; 4.1(e)). This means that C 1 and C 2 are far apart. In all other cases 0 < P i,j (C|a j ) < 1 (cf. This motivates us to draw a check on the relation between a j , l j and r. Towards this we first compare if a j + l j ≤ r. That is, if the total distance moved by the two nodes is smaller than transmission range r. If the condition holds, it means that D 2 encapsulates C 1 and thus P i,j (C|a j ) = 1 (cf. Fig. 4.1(a)). If the condition is not true then we compare if a j ≤ l j + r. This relates to the fact that the distance between the positions of i at time t + ∆t and j at time t + ∆t is less than r. If the condition is also true then there is a P i,j (C|a j ) > 0 (cf. Fig. 4.1(b)) as j will lie within the transmission range of i. However, if a j > l j + r then the P i,j (C|a j ) = 0 (cf. Fig. 4.1(c)). This means that node j at time t + ∆t is beyond the transmission range of i at time t + ∆t. Further, we check if a j + r ≥ l j , if the condition holds then P i,j (C|a j ) > 0 else the P i,j (C|a j ) = 0 (cf. Fig.

4.1(d) and 4.1(e) respectively).

Let E 1 be the event such that E 1 = {a j > l j + r or a j < l j -r} where P i,j (C|a j ) = 0 and E 2 be the event such that E 2 = {a < rl j } where P i,j (C|a j ) = 1. For computing P i,j (C|a j ) when the complement of event (E 1 E 2 ) occurs, let θ j denote the angle between the displacement vectors of node j and node i taking the location of node j at time t as the reference. Note that the displacement vector of node i (resp. node j) w.r.t. the location of node j at time t is given by i t+∆tj t (j t+∆tj t ). Using the law of cosine, θ j is given by Note that 0 ≤ θ j ≤ π.

θ j = cos -1 a 2 j + l 2 j -r 2 2a j l j . ( 4
The above discussion can be summarized into the following eq.:

P i,j (C|a j ) =            0 if E 1 , 1 if E 2 , 2θj aj 2πaj = θj π otherwise. (4.1.2)
We now remove the conditional probability about the knowledge of a j . In order to remove the condition about the knowledge of a j , a distribution of a j is needed. We remove the conditioning on a j by using the fact that the jump lengths are distributed according to a truncated power law. Let f A (a j ) be the distribution of a j given by eq. 2.7.1. Note that ∞ xmin f A (a j )da j = 1. We obtain the unconditional P i,j (C) as P i,j (C) = ∞ xmin f A (a j )P i,j (C|a i )da j . This reduces to

P i,j (C) =                                                                       lj +r lj -r f A (a j ) θ j π da j if l j -r ≥ x min lj +r xmin f A (a j ) θ j π da j if l j -r < x min                  if l j ≥ r                  r-lj xmin f A (a j )da j + lj +r r-lj f A (a j ) θ j π da j if r -l j ≥ x min lj +r xmin f A (a j ) θ j π da j if 0 ≤ r -l j < x min                  if l j < r                                                      (4.1.3)
Further, as the eq. 4.1.3 refers to the connection probability between i and its neighbor j ∈ N t i in t + ∆t, this probability directly relates to the probability of link occurrence between i and j ∈ N t i at t + ∆t. If P i,j (C) → 1, it means that the link is highly likely to exist at time t + ∆t. However, if P i,j (C) → 0, it means that the link may not exist at time t + ∆t.

The stability of node i is estimated by the ratio of the expected value of the number of links between node i and its neighbors in N t i that can exist at time t + ∆t over the number of neighbors that existed at time t. Thus, we define stability for a node i as

S * i = j∈N t i P i,j (C) |N t i | . (4.1.4)
Using the eq. 4.1.4, all the nodes in the network perform the stability estimation task independent of each other. This stability estimation does not require any global knowledge and can be achieved using local information available to the node.

Beamforming using S * i

As stated before, only few nodes with beamforming capabilities are needed to enhance the dissemination process [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF]. In order to determine the few beamforming nodes, we use the above proposed stability measure. Once a node i measures its stability, it then decides whether to beamform or not to beamform. If S * i < S min then i decides to switch its omnidirectional beam to directional beam. In order to let few nodes beamform we let S min to be a small. A S min = 1 will allow all the nodes to beamform, will cause lot of asymmetric links and a loss in clustering coefficient. A S min = 0 will allow no node to beamform. Hence, in order to have only few beamforming nodes S min should be small. An interpretation for choosing nodes that have S * i < S min to beamform in terms of information dissemination is: such nodes are more likely to have information from much bigger set of neighbors (case (ii) of S = 0 and case (i) of 0 < S < 1, as discussed at the beginning of the Chapter). However, note that due to the definition of S * i some nodes might have undefined stability because |N t i | = 0. We let such nodes to beamform also. The idea behind such a rule is, at time t a node i might be the source of information. As |N t i | = 0, node i will not be able to transmit the information until it gets connected to some other node at some time. Letting such node to beamform will ensure the information propagates from the node early.

After the decision of whether to beamform or not, it is necessary to determine which is the best direction to beamform and what are the beam properties (length and width). In the previous Chapter, we stated that there are some preferred nodes to which when beamforming is done network average path length can be reduced hence requiring less time to disseminate the information. In order to determine preferred nodes, we state that the nodes that have S * i > S max are the preferred nodes. As from the discussion in the beginning of the Chapter, when S = 1, (i) the node is still connected to all of its neighbors at time t and no new node has become its neighbor and (ii) the node is still connected to all of its neighbors at time t and new neighbors have joined. Further, when S * i > 0.5 it implies more than 50% of its neighbors at time t are still neighbors. Beamforming to nodes that have S * i > S max will let nodes with S * i > S max to get information from a bigger set of nodes thereby making them aware of more information flowing in the network. As the beamforming will increase the in-degree of the preferred nodes, the preferred nodes will be able to disseminate more information. Also, if the S * i is undefined, it means that |N t i | = 0. Further, we let such nodes to also be the preferred nodes. For a more clear understanding in Table 4.2 we present all possible combinations of stability measures for the nodes that should beamform and the nodes to which the beams should be directed.

Here we add the degree of a node i at time t to help explain the beamforming strategy.

Note that in a dynamic scenario the edges in the network are intermittent. The choice of beamforming node will change every time as it depends on the stability measure. This will cause different set of nodes to beamform at a given instant.

In the algorithm, we assume that m AEs are randomly selected from the available M AEs by the beamforming nodes. In order to determine the direction of the main beam, B b , the node sweeps 2π angles and determines the best direction as the direction in which maximum number of beamforming to nodes are found. While determining the best direction, we also condition that the hopcount between beamforming to nodes and beamforming nodes should be greater than 1. If beamforming to nodes are one hop away, beamforming will have no affect on enhancing the information dissemination process and will increase the network path length by reducing the neighborhood. If the node i is not able to find any beamforming to nodes more than one hop away, the node reverts back to the omnidirectional case.

Further, beamforming makes the network asymmetric. A node will be able to transmit the data but will not be able to receive the ACK for the transmission made. Also beamforming nodes will not be able to know if there are any beamforming to nodes in the region of directional beam. As we are just concerned about the dissemination of the information in a broadcast medium, the problem of asymmetry is of less importance. For the second problem, same as Chapter 3, we assume that the beamforming to nodes, just to let the beamforming node know about the connection setup, creates the beam in the direction of the beamforming node and then reverts back to omnidirectional scenario. Also note that as the network is directed, degree of a node can not be used to estimate the stability value. Towards this, we use in-degree of the node to compute stability.

Simulation Results

We use a simulation area of A = 500x500 to simulate the algorithm. We set the average density of nodes, ρ, to 1x10 -3 . Initially, each node operates in omnidirectional mode using m = 1 AE with the omnidirectional radius as r = 30. We set the maximum number of AEs that the nodes are equipped with to M = 6. The separation between two AEs is computed using W iF i frequency, f = 2.4Ghz.

We set α = 1.6, β = 300, x min = 1, S min = 2x10 -3 , S max = 0.7 and use a U LA antenna model to simulate the algorithm. Through the simulations, we explore the effect on time taken to disseminate the information in the network using various scenarios.

We validate the results and provide comparison between four different cases: (i) when a node i uses S * i with beamforming strategy as discussed in Section 4.1.3; (ii) when a node i uses stability measure S i as discussed in Section 2.8.6 instead of S * i with beamforming strategy as discussed in Section 4.1.3; (iii) when a node i does not use beamforming; and (iv) when choice of beamforming nodes and the beam direction is random but the number of nodes that beamform is same as that found by the algorithm. We refer to these cases as Case A, Case B, Case C and Case D respectively. Note that mobility is applied in all the four cases. For all the above mentioned cases we then simulate four different scenarios. These include: (i) single source having single packet to transmit; (ii) single source sending update information; (iii) multiple sources with each having single packet to transmit; and (iv) multiple sources with multiple packets where sources can join over time. Using these cases and scenarios we study the fraction of nodes having information at a given time and compare the differences. We also show the effect of various parameters on the time taken to disseminate the information in the network. We use Python to simulate the algorithm. We average the results for these cases and scenarios over 50 topologies for a T = 100. We use a confidence interval of 95%.

We first show the results obtained for the scenario when there is only one source having only one packet to transmit. In this scenario, a node is first randomly selected to be the source of information.

The selected node then generates a packet at t = 0 (start of the simulation). Fig. 4.2 shows an improvement achieved when the algorithm is used. The results show that in almost 30 time steps all nodes in the network have the packet when beamforming is done using Case A. We then plot the difference in the fraction of nodes having packets for different cases. Let I S * i be the fraction of nodes having packet at at a given time for Case A. Let I y be the fraction of nodes having packet at at a given time for other cases. Let y ∈ {S i , nobeam, randombeam}. Note that y denotes cases In the above scenario, the dissemination process starts as soon as the packet is generated. However, when an update is generated, the previous packet is now obsolete. All the nodes that received the first packet will now be considered as nodes not having the packet. The dissemination process will thus have a new initial starting condition. If the source node generates an update after t x time then the dissemination process effectively starts from t x . Further, if an update is again generated after another t x time, the effective starting point will now be 2t x . Fig. 4.3(a) is generated when there is only single source having an update packet to be transmitted in the network. Fig. 4.3(a) also shows an improvement achieved in this scenario. In this scenario, the initial packet is generated at t = 0 (start of the simulation) while the last update is generated at t = 10. Here time taken to completely disseminate the update has a shift by ≈ 10 time steps than the previous scenario, thereby confirming our explanation above. However, other observations for the fraction of nodes having the packet after t = 10 remains same to that of the previous scenario. From t ∈ [0, 10], there is a hill because the update packet is randomly generated between t ∈ [0, 10]. When an update packet is not generated, the network assumes that there is no update packet in the network and the dissemination of the previously generated packet occurs. Similar to the previous scenario, we also plot Further, we now assume that there are multiple sources each having single packet to disseminate in the network. This will increase the diversity of information in the network. We set the number of sources to be 40 for the next two scenarios dealing with multiple sources. Similar to the scenario of single source, all the sources generate the packet at t = 0. For this scenario, we define the fraction of nodes having the information as the set of nodes that have received all the packets from all the The time taken for all nodes to receive information from all the sources is max{T 1 , T 2 }, where T 1 and T 2 are the time taken for packets from source 1 and source 2. This is generalized for n sources where the total time taken for all the nodes to receive the information from all the sources is given by max{T 1 , T 2 , . . . , T n }. The results show that in ≈ 38 time steps the packets from all the sources can be disseminated in the network when beamforming is used using S * i . However, only ≈ 83% nodes have received all the packets for Case C (cf. Fig. 4.4(a)). As there are multiple sources, the fraction of nodes having all the packets has a shift in time. It takes ≈ 6 time steps for one node to have all the packets from all the sources for the beamforming case while ≈ 9 time steps when beamforming is not used. The time taken for all the nodes to receive the packets from all the sources, however, is ≈ 36 time steps for Case A. While only ≈ 77% nodes received all the packets in 36 time steps for Case C. We now show the difference in the fraction of nodes having packets, I S * i -I y , for different cases for this scenario (cf. In the above scenario number of sources were fixed and no other source was allowed to join the dissemination process. We now relax this assumption and allow sources to join as time progresses.

I S * i -I y (cf.
Similar to the previous scenarios, we define the fraction of nodes having the information as the set of nodes that have received all the packets from all the sources in the network. Fig. 4.5(a) is generated towards such scenario. We set a time limit until sources can join to t = 20 so that we can obtain the results in desired time. Here each source i randomly generates n i packets until t = 25 as in the previous scenario. The results show that in ≈ 60 time steps all packets can be disseminated in the network when beamforming is used with S * i . However, only ≈ 81% nodes have received all the packets for Case C (cf. shows the maximum improvement achieved over cases B, C and D is 0.068, 0.506 and 0.0597, respectively. Note that, when the population is large and spread in larger area (as in real country wide population), these differences on the actual population scale can be large. Further, results obtained for the multiple source scenario suggest that beamforming using S * i performs better than random direction beamforming.

In the above four scenarios, the fraction of nodes that beamform is shown in Fig. 4.6 for Case A.

From the results it is noted that for different scenarios the fraction of nodes beamforming remain mostly in the range 0.043 ± 0.006 (cf. Fig. 4.6). This is because the selection of the beamforming nodes is independent of the number of sources in the network.

We next provide results for varying ρ, α, β, r, M , S min , S max and antenna type when there are multiple sources that have multiple packets to transmit and sources can join. Through this set of simulations we show the effect of the aforementioned parameters on the information dissemination process when the algorithm is used. We first provide the effect of varying ρ on the dissemination process. Note that all other parameters are kept constant. As ρ increases, the number of time steps taken to disseminate the packet reduces, (cf. Fig 4.7(a)). This is because (i) when ρ is high more nodes are in the giant connected component and the connectivity is high and (ii) the average number of connections for a node is higher. This enables a node to forward the information to more nodes.

Varying α, it is observed that when α is high the time taken to disseminate the information in the network also increases, (cf. Fig. 4.7(b)). This is because as α increases the number of long jumps decreases and there are more short jumps. When jumps are short devices are not able to meet other devices as frequently as when α is less. Varying β, variations in time taken for all the nodes to receive the information is shown in Fig. 4.7(c). For small β, i.e. when the jump length cutoff is small, the nodes are not able to move far. This affects the nodes meeting different nodes in the network. Thus more time is required to disseminate the information in the network. While when β is high, the nodes are able to move far and meet more nodes and disseminate the information in the network much faster. Note that in the above two sets of simulations all the other parameters are kept constant.

Parameter Time taken value value

ρ ↑ ↓ α ↑ ↑ β ↑ ↓ r ↑ ↓ m ↑ ↓ Smin ↑ ↓ Smax ↑ ↑

Conclusion

In this Chapter, we propose an algorithm that can enhance information dissemination in terms of number of nodes having the information in less time in mobile scenarios. There are three main contributions in this Chapter. First, in this Chapter we propose a probabilistic approach to compute the stability of a node in a mobile environment. Second, based on the stability measures beamforming is performed and we show that large number of nodes can receive the information quickly in the mobile environment when compared to other related studies. Third, the algorithm operates in an environment where nodes do not require any global knowledge of the network, takes decisions autonomously and requires less memory to operate.

The results show an improvement in the information dissemination process when the proposed stability measure is used over three different cases including the case when there was no beamforming and when nodes were randomly chosen to beamform. Moreover, our proposed stability measure does not require the entire history of links. It only requires latest link status, i.e. links at time t to compute stability at time t+∆t. The algorithm works in fully decentralized manner with no entity controlling the decisions made by the nodes. The results show that information dissemination is affected by many parameters, such as number of sources, number of packets, mobility parameters, density, radius of communication, number of antennas, antenna type, stability parameters and stability type used.

in Chapter 4 and other device characteristics [START_REF] Wang | Information Spreading in Context[END_REF]. However, as noted in [START_REF] Kivelä | Multiscale Analysis of Spreading in a Large Communication Network[END_REF], the characteristics of the human mobility impact the dissemination process the most when compared to others.

For a countrywide scale mobility pattern, we use the data provided by the Data for Development (D4D) group and Orange Labs [START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF]. The analysis of the dataset reveals that in a large population, communities are formed. The density of the population per community changes over time due to the movement of individuals from one community to another. Such an organization of a large population into community structure where the interaction between the communities is based on the mobility, has already been studied through a synthetic model of population called metapopulation [START_REF] Arino | Disease Spread in Metapopulation[END_REF][START_REF] Watts | Multiscale, Resurgent Epidemics in a Hierarchical Metapopulation Model[END_REF].

It has also been discussed that communities formed in a large population affect the dissemination process. An individual, if restricted to a community, will not be able to move freely to other communities. This will affect the message dissemination process. For example, the movement of individuals from one country to another country is restricted by the border controlling officers. Fig. 5.1 shows the difference in the number of people having information when c communities are present and when there is only one large community. The results are normalized by the total number of people N . Initially, a large difference in the curves is noticed because more people meet other people when they are not restricted to certain community and thus the dissemination process is fast. Also, the rate of spreading information in each community is different. Some communities are more resistant to the dissemination process while some are not. We assume similar features in our model too. Recently, in [START_REF] Lund | Effects of City-Size Heterogeneity on Epidemic Spreading in a Metapopulation: A Reaction-Diffusion Approach[END_REF], it is shown that not only the community structure affects the dissemination process but the density of the communities also has an important role in the dissemination process.

In communication networks, dynamic density can be achieved using two scenarios. First, addition and removal of devices and second, sleep and wake process. We are interested in investigating how the information dissemination process at the countrywide scale is impacted and how it can be enhanced in a variable density scenario due to sleep and wake type variation alone (not considering addition and removal of devices). To capture the variable density effect, we use the Latent state (E). To distinguish between devices that are Latent but Susceptible, Latent but Infected and Latent but Recovered, we subdivide E into three states: E S , E I and E R . Devices in E S , E I and E R states do not participate in the dissemination process. Only active devices in S, I and R states participate The datasets provided by the D4D group includes the information about the user mobility and the association of a user to a community, termed as subprefecture, in the region of Ivory Coast. In order to study the model on a countrywide population, we use the population data provided in [144] to populate the subprefectures in the country of Ivory Coast. In Ivory Coast, a group of subprefectures form a department, collection of these departments form a region and collection of these regions form the country. In this Chapter, however, we are more interested at the subprefecture level as the dataset contains the mobility patterns at that level. More details on how mobility patterns are calculated using the dataset are provided in Section 5.2.2 and in Appendix B.

Based on the context and proximity information, a device discovers other devices in its physical proximity and establishes a link with them [START_REF] Corson | Toward Proximity-Aware Internetworking[END_REF]. In some situations, a device acts as a relay in a multi-hop D2D communication scenario. This increases the network coverage because the information can now be transmitted to the devices beyond the coverage zone and even in a poor cellular coverage zone. Based on the context, devices can also form groups, where a device can act as a leader or the member of a group. Using collaborative forwarding mechanisms, the devices within a group share data efficiently for optimized resource utilization and higher throughput [START_REF] Golrezaei | Base-Station Assisted Device-to-Device Communications for High-Throughput Wireless Video Networks[END_REF].

A device in a network, however, can be equipped with an antenna array with multiple antenna elements embedded in some geometrical pattern, e.g., linear or circular. When a device uses multiple antenna elements, larger transmission range with certain angular coverage is achieved due to constructive and destructive interference in the radiation from the antenna elements. The technique whereby multiple antenna elements are used to achieve larger transmission range is known as beamforming. The effects of beamforming have already been studied on the information dissemination process for both static and mobile networks with positive results [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Li | Collaborative Vehicular Content Dissemination with Directional Antennas[END_REF] (Cf. Chapters 3 and 4) and considerable enhancement in the dissemination process is achieved with a few devices beamforming. We use the idea of a few devices beamforming, mobility and the proposed six state model, and show how it can help in enhancing the dissemination process.

In a human population, a user is associated with a home location. Every time a user moves away from its home location it has a rate to return to its home location from its new location. We thus update the mobility model to incorporate rate of return for a user to return to its home location. This return rate is also derived from the D4D dataset. More details on how the return rates are computed are mentioned in Section 5.2.2. Using two different mobility models (with and without home locations) we then show the effect of the mobility models on the dissemination process. Thus, in this Chapter, we use insights from the dissemination in the metapopulation model, data provided by the D4D organizers, epidemic model and beamforming to develop the analytical model.

A table of notations and their meanings as used in this Chapter, hereafter, is provided as Table 5.1.

The remainder of this Chapter is organized as follows. In Section 5.1 we first provide an overview of the D2D scenario. In Section 5.2 we describe how the dataset provided by the D4D organizers is used to get useful information. A detailed description of the model is then provided in Section 5.3 which is followed by the results obtained in Section 5.4. The Chapter finally concludes with Section 5.5.

Notation Meaning

Area

area of the country.

A i area of community i|i ∈ C, ∀i A i = Area A b,q
Area under the beam for the beamforming device q

Loosely Controlled D2D Support for Information Dissemination

We assume the following D2D scenario. Using a Public Warning System (P W S), a national emergency warning has to be broadcast by some eN B (evolved Node B, a radio interface in Long Term Evolution (LT E) network) and should reach the maximum number of people in the country. However, in such situations, the operator's network is massively overloaded by a huge traffic of users trying to use their mobile devices at the same time. Also, the warning message may not reach a part of the population due to network coverage issues in rural zones. Using D2D communication, devices communicate directly with other devices in the physical proximity and transmit the information.

This mechanism not only allows the extension of the broadcasting area but also enhances the traffic on the network infrastructure and avoid network saturation and waste of resources.

A D2D communication has two phases: the Neighbor Discovery phase and the Communication phase for the data exchange. A neighborhood discovery can be based on either direct discovery or a network assisted discovery. In some studies related to D2D communication systems, these discovery models are also called distributed and centralized discovery, respectively [START_REF] Fodor | Design Aspects of Network Assisted Device-to-Device Communications[END_REF][START_REF] Lei | Operator Controlled Device-to-Device Communications in LTE-Advanced Networks[END_REF].

In the distributed approach, each device sends beacons to all devices in its surrounding to an- nounce its presence. This approach is highly scalable as the operator has less control on the communication between the devices and does not control the QoS of the communication. This approach is also a solution to avoid communication disruption when some eN Bs are down in a disaster situation like Earthquake or when an eN B fails. The users could still use their devices and be connected to the operator network using direct communication. However, in such D2D loosely-controlled mode, operators could face several issues like performing lawful interception, ensuring the security of the data transfer when devices are exchanging the information directly and whether the communication and discovery should be allowed on the licensed or unlicensed spectrum [START_REF] Fodor | Design Aspects of Network Assisted Device-to-Device Communications[END_REF][START_REF] Doppler | Device-to-Device Communication as an Underlay to LTE-Advanced Networks[END_REF].

In the centralized approach, however, some entities in the operator core network could be responsible for the peer discovery phase and the communication phase. For instance, the eN B can be informed about the devices that are in the physical proximity and could provide the devices with the necessary authentication and resource configuration to setup a D2D link. Nevertheless, this approach is less scalable than the distributed approach as the network could face load balancing issues in handling huge number of D2D links.

Using a loosely controlled D2D mechanism, some eN Bs can allow direct communication between devices that are in physical proximity. Fig. 5.2 shows, some eN Bs allowing the direct communication between devices that are in physical proximity while some do not. Fig. 5.2 also shows that a device could move from one eN B to another. However, the device could also move within the associated eN B. In this Chapter, we assume that all eN Bs allow direct communication between devices that are in physical proximity. Let a public warning message be generated in some area associated to an eN B. In this Chapter, we are interested in investigating how fast dissemination of the warning message can be achieved through a large population in a D2D environment where the devices are also mobile and links are intermittent. By fast dissemination we mean how, after the warning message is generated, a large set of devices can quickly receive the warning message.

Data

In this Section we extract useful information from the data collected by Orange Labs for the region of Ivory Coast. The data is based on the calls made by using mobile devices in the region of Ivory Coast [START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF]. Ivory Coast is divided into a number of regions which are subdivided into departments where departments are again subdivided into subprefectures. A subprefecture contains antennas. Another dataset (SET2) contains similar information as SET3. SET2, however, is much smaller as compared to SET3 and contains relatively fine grain information than SET3. SET2 contains tuple with information antennaID from where the call was made, time when the call was made and userID of a person who made the call. However, SET2 contains information for only 50,000 users over 5 months from 5th December 2011 until 28th April 2012. Thus, we are interested in SET3 as it is bigger and is well complemented by the subprefecture location dataset (SPLoc).

Dataset Subprefecture Locations (SPLoc)

Interpreting SET3

As stated before, mobility of a user can be interpreted and estimated using SET3. We map the mobility of the user on a complete graph (G c ) formed by connecting all the subprefectures to all other subprefectures and also map the mobility of the user on G v . As human mobility often observes few long jumps to communities that are not near (neighbors), it is essential to map the mobility pattern of the users on G c . However, the mapping of the mobility of the user on G v provides the route which the user might have taken while it moved. marks the starting point of the track followed by the user. Let us consider G v first. To track a user on G v , first the shortest path, SP u1u2 , between u 1 and u 2 in G v is found. This process is done for all consecutive pair of entries in U . Each entry in the shortest path provides the information about the subprefecture that the user would have encountered while moving from u 1 to u 2 . Let

SP u1u2 = (u 1 , u x , u x+1 • • • , u 2 )
. Note that the successive subprefectures in SP u1u2 are connected by an edge in the graph G v . If u 1 = u 2 , it is inferred that the user has not moved.

Let C be the set of subprefectures. For user u, let P u be a weight matrix of size |C| × |C| where (P u ) ij represents the weight of the edge between i and j. We initialize P u as (P u ) ij = 0, ∀i, j ∈ C.

Consider the shortest path SP u1u2 between two consecutive entries in U . (P u ) ij is incremented by 1 if the edge from i to j is encountered in the shortest path SP u1u2 . Note that i and j corresponds to a pair of successive entries in SP u1u2 . This process is then repeated for SP u2u3 and so on until all elements in U have been considered. If u 1 = u 2 , then we increment (P u ) u1u1 by 1. Users are also tracked on G c using the same method.

As an example, we track the user u = 297412 in the SET3 dataset on both G v and G c (cf. Fig.

5.4(a) and 5.4(b)

). In Fig. 5.4 the blue edges mark the edges that user traversed. The thickness of the edges is equal to the number of times a user traversed through that edge. We also call it as the weight of the edge. The size of the node in the graph is equal to the weight of the node, (P u ) ii . The yellow node marks the subprefecture k which satisfies

k = arg max ∀i∈C {(P u ) ii } .
The above process is performed for all the users in the SET3 dataset for the entire time period and the weights of the edges are determined for both G v and G c . Let P = ∀u P u .

We now create the conditional Probability Matrix for movement, M P v , and the Rate Matrix for movement, M R v , from P that are obtained while tracking users on G v . Further, we create the conditional Probability Matrix for movement, M P c , and the Rate Matrix for movement, M R c , from P that are obtained while tracking users on G v . As the method to obtain M P v and M P c are same, we only explain how M P v is obtained. In P , let P ii = 0 for all communities i as we are interested in the conditional probability of movement into and out of communities and not how long they stay there.

Definition 5.2.1. M P v is a |C| × |C| matrix where the ij-th element represents the conditional probability of moving from subprefecture i to subprefecture j given that it has moved out of subprefecture i. We have, for all i = j,

(M P v ) ij = (P ) ij ∀k∈C (P ) ik . ( 5

.2.1)

We now describe the method to obtain M R v and M R c . As the method to obtain M R v and M R c are the same, we only explain how M R v is obtained.

Definition 5.2.2. M R v is a 1 × |C| matrix where the i th element represents the rate of moving out of subprefecture i. We have, for all i ∈ C,

(M R v ) i = ∀k∈C (P ) ik T ime (5.2.2)
where T ime = 150 × 24 × 60 minutes, the total duration in minutes over which SET3 was generated.

The matrices M P v and M P c are shown in Fig. 5.5(a) and 5.5(b). Note that because the number of edges are less in G v than G c the M P v is more sparse than M P c .

We now generate the Return Rate matrices, M RR v and M RR c , i.e., the rate at which the user returns to its home subprefecture which is defined as follows.

Definition 5.2.3. Recall the list U = (u 1 , u 2 , . . . , u n ) defined earlier for user u. For all j ∈ C and

1 ≤ i ≤ n, let Z ij be the indicator variable such that Z ij = 1 if u i = j and Z ij = 0 otherwise. Let M j = n i=1 Z ij .
Note that subprefecture j appears exactly M j times in the list U . The home subprefecture, H, of the user u is the subprefecture k that satisfies

k = arg max ∀j∈C M j .
We now describe the steps for generating M RR v . Consider the home subprefecture H of a user u. Let P r u be a weight matrix of size |C|×|C| similar to the weight matrix P u with the only difference being that the increment now is done whenever a user jumps to H from any other location j = H, i.e., we increment (P r u ) jH by 1. We then perform the same task for all the users and determine P r = ∀u P r u .

Definition 5.2.4. M RR v is a |C| × |C| matrix where its ij-th entry represents the rate of coming back to the home subprefecture j from another subprefecture i. For each i, j ∈ C, we have

(M RR v ) ij = (P r ) ij T ime ,
where T ime = 150 × 24 × 60minutes.

Steps for generating M RR c are similar. Note that H for a user will be same for G v and G c . As an example, here we only provide the return rate matrix for G c (cf. Fig. 5.5(c)).

The information in SET3 can be used to infer the density of people in subprefecture over time.

A tuple in SET3 provides which user is associated to which subprefecture at a certain time. Using this information we determine the density of each subprefecture at a certain time. From SET3 using query "SELECT DISTINCT time FROM SET3" a set of all distinct times in the SET3 are extracted. We then generate a matrix P d with distinct times as row indices and subprefectureIDs as column indices. Note that the distinct times in SET3 have a granularity of 1 minute (which forms the natural bin size). We initialize P d with a zero matrix. We then read tuples in SET3 one by one and add 1 to the (P d ) time,subpref ectureID for each tuple.

Definition 5.2.5. The density matrix, M D, is defined as

(M D) time,subpref ectureID = (P d ) time,subpref ectureID A subpref ectureID (5.2.3)
where A subpref ectureID is the area of a subprefecture in Ivory Coast.

In Fig. 5.6 we provide a visual representation for the density of users on a log scale for the period from 16th December 2011 starting at 00:00:00 until 31st December 2011 ending at 23:59:00 1 . Fig. 5.6 shows that the number of calls is high during the day time while it is low during the night time.

In a D2D perspective this change in density causes the network structure to change over time which provides us the motivation to incorporate the changes in the density through the concept of Latent States explained in Section 5.3.

1 An animated version of active number of users from 16th December 2011 starting at 00:00:00 until 31st December 2011 ending at 23:59:00 can be viewed at http://complex.luxbulb.org/content/d4d-challenge We will now describe the dissemination model using M P c and M R c in the next Section.

Model

We represent our model in three layers. The bottom layer is the population layer where population of devices is spatially divided into communities. Above the population layer is the mobility layer where devices are allowed to move from more community to another with the rates extracted from the SET3. The dissemination model is then applied on the top of the mobility model. Thus, each device is associated to a community and a epidemic state (S, I or R).

Consider a set N of devices, |N | ∈ N, that are non-uniformly distributed in a region of area Area, Area ∈ R + and Area > 0. The non-uniformity leads to a community structure in the region.

We assume that the set of these communities, C, is the set of subprefectures in the Ivory Coast. Let N i be the number of devices that are in community i such that ∀i∈C N i = N . Let A i be the area of the community i such that ∀i∈C A i = Area. Let density ρ i = Ni Ai .

Mobility Model

In a D2D context a subprefecture can be envisioned as an eN B where the eN Bs have allowed the D2D communication. At a given time, a device is associated to one and only one eN B, i. From the dataset, |C| = 255. Further, as argued by Watts et al., community structure is evident in the population in a realistic scenario [START_REF] Watts | Multiscale, Resurgent Epidemics in a Hierarchical Metapopulation Model[END_REF]. The movement of a device or the jump of a device from a community i to another community j occurs with a rate σ i ν ij where σ i denotes the total rate out of community i and ν ij denotes the conditional probability of going to community j given that there is a transition out of community i. It was also shown that the jump also depends on the nature of the community [START_REF] Wang | Safety-Information-Driven Human Mobility Patterns with Metapopulation Epidemic Dynamics[END_REF] and the activity pattern [START_REF] Liu | Contagion Dynamics in Time-Varying Metapopulation Networks[END_REF]. This rate plays an important role in determining which new community has to be joined by the device. As each device is carried by humans this allows us to state that each device closely follows the mobility pattern of humans. Towards this, we use (M R c ) i calculated in Section 5.2.2 to determine if the device has moved out of community i or not. The device then has a conditional probability to go to the desired community. We use (M P c ) ij as the conditional probability to go from community i to community j. Note that the devices can move within the bounds of a community, but it does not affect the parameters that describe inter-community movement. However, the contact rate between devices moving inside the same community is affected by this intra-community movement. We shall see that the contact rates affect the rate of message dissemination in the same community.

Definition 5.3.1. We assume that the random time spent in community i, called the dwell time in community i, is exponentially distributed with mean 1 σi . The rate of going out of community i is defined by σ i = (M R c ) i . Note that when σ i → ∞ it means that the device does not stay in i and the movement out of the community occurs instantaneously. However, when σ i → 0, it means that a device stays permanently in community i. Definition 5.3.2. The conditional probability to move to community j given that there is a transition out of community i is defined by ν ij = (M P c ) ij where ∀j∈C ν ij = 1 and ν ii = 0. Fig. 5.7 shows a mobility model with only three communities where movement from one community i to another community j is represented with an edge defined by σ i ν ij . All other notations for movements are similarly defined. Note that each community i in the above model consists of devices is thus defined as

N * i = ∀j∈C,j =i σ j ν ji N * j σ i . (5.3.3)
At the steady state,

ρ * i = N * i
Ai where ρ * i is the density of devices at steady state.

Dissemination Model

We now describe the dissemination model. Let each device in a community be in either of the three states S, I and R. Note that these states are different from the communities to which the devices are associated to. State S means that the device does not have the information. State I means that the device has the information and is transmitting it. State R means that the device has the information and is not transmitting it. Let S i , I i and R i be the number of devices in state S, I and R, respectively, in community i at time t. As we apply the dissemination model on top of the mobility model where we approximated the number of devices by the steady state limit, it should be noted that

N * i = E[S i ] + E[I i ] + E[R i ].
Under the mean field assumption, we can safely assume that N * i will remain constant over the simulation duration. Let each device have an omnidirectional transmission range, r such that r ∈ R + . Due to the transmission range each device has a neighborhood in the community i to which they can communicate. We assume the interactions among the devices to occur under mean field approximation where the expected neighborhood size is given by k i . Definition 5.3.3. The expected neighborhood size for a device in a community i is defined as

k i = ρ * i πr 2 .
In real scenarios, communities affect the global dissemination of the information. In a system with a community structure, the information transfer is bounded within the community unless a device in the community moves to another community. This makes us to constrain the devices in state I to be able to only transmit the information to the devices in the associated community (in associated eN B) that are in state S and are within their transmission range or the physical proximity, i.e., a device in state I will be able to transfer information to k i device in its neighborhood. Note that some devices in k i might already have the information. In such case the device would not be able to transfer information to that device.

Definition 5.3.4. The transition rate with which a message is received successfully is given by β such that β ∈ R + . It can also be understood as the contact rate between two devices.

We assume that the devices in different communities have different β represented as β i . This is because of many factors like, the density of the population and willingness of other devices to accept the transmitted information. This idea is analogous to the epidemic spreading in different communities which happen at different rates. Thus, devices in each community have different contact rate.

Due to the energy constraints, a device can only transmit information for a certain period of time after which the device does not transfer the information. This can be understood as the rate with which devices change their state from I to R.

Definition 5.3.5. ∀x associated with community i, the rate with which devices in community i change their state from I to R is given by δ i such that δ i ∈ R + .

The β i and δ i associated with a device change when the device moves from one community to another. This can be understood as when a device moves from one community to another its willingness to transmit the information or not to transmit the information may increase or decrease.

In a community i, let initially at time t = 0, S i = N * i , I i = 0 and R i = 0. In order to study the dissemination process, let one community i at time t = 0 be the source of information, i.e., S i = N * iε, I i = ε and R i = 0 where 0 < ε < N . Under mean field approximation, S i I i /N * i provides the fraction of interactions between devices in state S and devices in state I. As each device has a neighborhood k i and the contact rate between devices is β i , the number of devices that will change their state from S to I is given by

β i SiIi ki N * i .
Let us consider the change in the number of devices in state S. Due to mobility, some devices in state S will move from other communities to community i while some devices in state S will move from community i to other communities.

The number of devices moving from other communities to i is given by ∀j∈C,j =i σ j ν ji S j while those moving from i to other communities is given by σ i S i . Thus the rate of change in the number of devices in state S in community i in dt time is given by

dS i dt = -β i S i I i k i N * i + ∀j∈C,j =i σ j ν ji S j -σ i S i .
Using such interpretation and above explanation the rate of change in the number of devices in state I and state R can be formulated. We define the rate of change in number of devices in state S, I and R in community i as

dS i dt = -β i S i I i k i N * i + ∀j∈C,j =i σ j ν ji S j -σ i S i dI i dt = β i S i I i k i N * i + ∀j∈C,j =i σ j ν ji I j -σ i I i -δ i I i dR i dt = δ i I i + ∀j∈C,j =i σ j ν ji R j -σ i R i                      (5.3.4)
In eq. 5.3.4, the fourth term in dIi dt represents the number of devices changing their state to R. Note that the set of equations in eq. 5.3.4 is for one community. As there are |C| communities the actual number of equations in eq. 5.3.4 will be 3 × |C|. Further, note that due to steady state of mobility, ∀j∈C,j =i σ j ν ji S j + ∀j∈C,j =i σ j ν ji

I j + ∀j∈C,j =i σ j ν ji R j -σ i S i -σ i I i -σ i R i = 0.
As we are interested in knowing how many devices are in state I over time, we do not determine the steady state of dissemination. However, we study the transient states.

Adding Latent States

Irrespective of whether a device is in state S, I or R, the capability of the device to transmit or receive also depends on whether the device is switched on or off. It is possible that a device has the information but has been switched off by its user. This hampers the transmission of the information from the device to other devices. Following the same argument, if a device does not have the information and it is switched off it will not be able to receive the information from other devices.

We call such state of a device as latent state and term them as E S , E I and E R to represent latent states pertaining to each active state, S, I and R respectively. When a device is switched on, this will mark the transition in the state of the device from either E S , E I or E R to S, I or R respectively. Definition 5.3.6. The transition rate to change the state from S to E S in a community i is defined as µ Si such that µ Si ∈ R + . The transition rate to change the state from I to E I in a community i is defined as µ Ii such that µ Ii ∈ R + . The transition rate to change the state from R to E R in a community i is defined as µ Ri such that µ Ri ∈ R + . The transition rate to change the state from E S to S in a community i is defined as α Si such that α Si ∈ R + . The transition rate to change the state from E I to I in a community i is defined as α Ii such that α Ii ∈ R + . The transition rate to change the state from E R to R in a community i is defined as α Ri such that α Ri ∈ R + . Further, a device in state E I can wake up and decide not to transmit information. Definition 5.3.7. The transition rate to change the state from E I to R in a community i is defined

as γ i such that γ i ∈ R + .
Note that due to addition of three new states,

N * i = E[S i ]+E[I i ]+E[R i ]+E[E Si ]+E[E Ii ]+E[E Ri ]
. Similar to initial condition as in Section 5.3.2, we assume at time t = 0

S i = N * i -ε, I i (t = 0) = ε and R i (t = 0) = E Si (t = 0) = E Ii (t = 0) = E Ri (t = 0) = 0,
where 0 < ε < N and t is the starting time.

Thus, the state diagram for this case is given by Fig. 5.8. This addition of latent states lead us to modify the equations mentioned in the eq. 5.3.4 for a community i to

dS i dt = -β i S i I i k i N * i + ∀j∈C,j =i σ j ν ji S j -σ i S i -µ Si S i + α Si E Si dI i dt = β i S i I i k i N * i + ∀j∈C,j =i σ j ν ji I j -σ i I i -δ i I i -µ Ii I i + α Ii E Ii dR i dt = δ i I i + ∀j∈C,j =i σ j ν ji R j -σ i R i -µ Ri R i + α Ri E Ri + γ i E Ii dE Si dt = µ Si S i -α Si E Si + ∀j∈C,j =i σ j ν ji E Sj -σ i E Si dE Ii dt = µ Ii I i -α Ii E Ii -γ i E Ii + ∀j∈C,j =i σ j ν ji E Ij -σ i E Ii dE Ri dt = µ Ri R i -α Ri E Ri + ∀j∈C,j =i σ j ν ji E Rj -σ i E Ri                                                    (5.3.5)
Note that the set of equations in eq. 5.3.5 is for one community. As there are |C| communities the actual number of equations in eq. 5.3.5 will be 6 × |C|. Further, it can be noted that there will be a growth in the population of devices in

I if β i S i I i k i N * i -δ i I i -µ Ii I i + ∀j∈C,j =i σ j ν ji I j -σ i I i +α Ii E Ii > 0.
Due to the addition of latent states the information dissemination is highly impacted. Let the case explained in the Section 5.3.2 be case A and the case explained in this Section be case B. We will maintain this nomenclature throughout this Chapter. The difference in number of devices in state I for case A and case B at a given time can be formulated. Let I i,t,A and I i,t,B be the number of devices in state I community i at time t for case A and B respectively. The difference in the number of devices in state I between two cases A and B can be computed as ∆I i (t) = I i,t,A -I i,t,B .

Using the initial condition, it is known that I i,0,A = I i,0,B . The difference in the number of devices in state I for all the communities is defined as ∆I(t) = i∈C ∆I i (t). As stated in Section 5.3.2 here also we study the transient states of the dissemination.

Adding Beamforming

As we are interested in enhancing information dissemination, one way of enhancing the information dissemination in a community based model is by the introduction of mobility. Another way of enhancing dissemination process studied in literature is through beamforming. Effects of beamforming have already been studied on the information dissemination process in the static population in 123

Chapter 3 as well as on the mobile population Chapter 4 and in [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Li | Collaborative Vehicular Content Dissemination with Directional Antennas[END_REF] with positive results.

In this Subsection, our objective is to apply beamforming to improve information dissemination.

We assume that each device is equipped with an antenna array with M antenna elements (AEs, each capable of achieving omnidirectional transmission range r) such that M ∈ N, where M can be different for different devices. Initially, all devices use one AE for omnidirectional transmission.

Here, r can be different for different devices. As we are interested in studying the benefits on information dissemination while using directional antenna, we assume path loss exponent to be equal to 2 and assume free space propagation. Further, only the devices in state I are allowed to beamform. In [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Li | Collaborative Vehicular Content Dissemination with Directional Antennas[END_REF] and in Chapter 4 it has been shown that considerable enhancement in the dissemination process can be achieved using very few long range links. Using this result, we state that only x% of the devices in the state I are randomly chosen to beamform. The selected devices randomly choose m ∈ [2, M ] AEs from M available AEs and beamform in a random direction. In the model, we use Uniform Linear Array Antenna model (U LA) [START_REF] Balanis | Antenna Theory-Analysis and Theory[END_REF].

Adding beamforming to the model only changes k i , as x% devices beamform. In terms of D2D communication scenario, k i relates to the number of D2D links for the device. Let k * i be the new expected neighborhood size in a community i after beamforming is added. k * i is modeled using the expected number of devices under the beam in the community i. Let X be the set of x% devices in community i that beamform. Let the antenna gain be g(q, θ, B b ) in the direction θ such that q in X with the antenna boresight direction as B b . The total area covered under the beam of q in X is given by A q = r 2 2 2π 0 g(q, θ, B b )dθ. Note that the gain in at the reception side is considered to be 1. For a device q in X, its k i,q = ρ i A q . Thus, for all the devices in X, k X,i = q∈X k i,q |X| . This implies k X,i = ρ i q∈X A q |X| . Note that the assumption here is that the area covered by the beamforming device lies within the area of the community the device is associated to.

Definition 5.3.8. When x% of the devices in the community i have expected number of connections k X,i while others have k i , the overall expected number of connections in a community i is defined

as k * i = ki (N * i -|X|)+ kX,i (|X|) N * i .
As only k * i has changed, the rate eq. 5.3.5 are now defined using k * i instead of k i . The new Figure 5.9: Associating return rate to the mobility model. The dotted line shows the return rate from another community and is marked with ζ c ′ c and dotted line, rate of moving out of a community is given by σ c , while rate of going out to another community is marked with σ c ν cc ′ and solid lines. Each community has associated number of devices. For different communities these devices are marked in different color (white for i, red for j, blue for k). The color of the lines also represent which community the devices are associate to.

community i instantaneously after visiting community j. However, when ζ ji → 0, it means that a device never moves back to its home community.

Note that ∀i ∀j

N ij = N . As represented in Fig. 5.9 the travel pattern leads to [START_REF] Sattenspiel | A Structured Epidemic Model Incorporating Geographic Mobility among Regions[END_REF] dN ii dt = ∀j∈C,j =i

ζ ji N ij -σ i N ii dN ij dt = σ i ν ij N ii -ζ ji N ij        (5.3.8)
The first term on the right hand side of the first equation in eq. 5.3.8, that is,

∀j∈C,j =i ζ ji N ij ,
relates to the number of devices returning to their home community i from other communities while the second term of the same equation, that is, σ i N ii , refers to devices that are moving out of community i that have home community i. The second equation in eq. 5.3.8 can also be similarly explained. Note that similar equations apply to all other communities. Also note that the total number of such equations is |C| × |C| and

N i = N ii + j∈C,j =i N ij = j∈C N ij and j∈C N i = N .
As described in Section 5.3.1, we first determine the steady state of mobility and then study the transient states in the dissemination process using the steady state population. Using eq. 5.3.8 the number of devices in the steady state is given by [104]

N * ii = N * i 1 1 + σ i ∀k∈C,j =i ν ik ζ ki N * ij = N * i   σ i ν ij ζ ji 1 + σ i ∀k∈C,j =i ν ik ζ ki                (5.3.9)

Dissemination model

The addition of return rates cause the system to change whereby new set of equations for dissemination process are to be written. Similar to the explanation of N ii and N ij , let S ii , I ii , R ii , E Sii , E Iii and E Rii be the number of devices in state S, I, R, E S , E I and E R , respectively, that have the home community as community i and are in the community i while S ij ,

I ij , R ij , E Sij , E
Iij and E Rij be the number of devices in state S, I, R, E S , E I and E R , respectively, that have the home community as community i and are in the community j. Thus,

N * i = ∀j∈C N * ij = ∀j∈C S ij + I ij + R ij + E Sij + E Iij + E Rij .
The new rate equations for the change in number of devices in state S, I, R, E S , E I and E R are given as

dSii dt = -βi k * i N * i ∀j∈C SiiIji + ∀j∈C,j =i ζjiSij -σiSii -µS i Sii + αS i ES ii dSij dt = -βj k * j N * j ∀q∈C SijIqj + σiνijSii -ζjiSij -µS j Sij + αS j ES ij        dI ii dt = β i k * i N * i ∀j∈C S ii I ji + ∀j∈C,j =i ζ ji I ij -σ i I ii -δ i I ii -µ Ii I ii + α Ii E Iii dI ij dt = β j k * j N * j ∀q∈C S ij I qj + σ i ν ij I ii -ζ ji I ij -δ j I ij -µ Ij I ij + α Ij E Iij          dR ii dt = δ i I ii + ∀j∈C,j =i ζ ji R ij -σ i R ii -µ Ri R ii + α Ri E Rii + γ i E Iii dR ij dt = δ j I ij + σ i ν ij R ii -ζ ji R ij -µ Rj R ij + α Rj E Rij + γ j E Iij        dE Sii dt = µ Si S ii -α Si E Sii + ∀j∈C,j =i ζ ji E Sij -σ i E Sii dE Sij dt = µ Sj S ij -α Sj E Sij + σ i ν ij E Sii -ζ ji E Sij        dE Iii dt = µ Ii I ii -α Ii E Iii + ∀j∈C,j =i ζ ji E Iij -σ i E Iii -γ i E Iii dE Iij dt = µ Ij I ij -α Ij E Iij + σ i ν ij E Iii -ζ ji E Iij -γ j E Iij        dE Rii dt = µ Ri R ii -α Ri E Rii + ∀j∈C,j =i ζ ji E Rij -σ i E Rii dE Rij dt = µ Rj R ij -α Rj E Rij + σ i ν ij E Rii -ζ ji E Rij                                                                                                         (5.3.10)
Thus, the total number of equations in the system being 6 × |C| × |C|. From the eq. 5.3.10 the total number of devices in state I for a community i that have home community as community i is defined by ∀j∈C I ij . Thus, the total number of devices in state I in all the communities is given by ∀i∈C ∀j∈C I ij . Similarly the number of devices for other states can be computed.

Simulation Results

The simulations are performed using the Python environment. Initially, each device operates in omnidirectional mode using m = 1 AE. The maximum number of antenna elements that any device could be equipped with is set to M = 5 with transmission range r = 0.5km. We assume free space propagation with path loss exponent equal to 2. The separation between two AEs is computed using W iF i frequency, f = 2.4Ghz. We consider, N = 15686986 in an area of Area ≈ 323096km 2 (Ivory public warning message across a large population. Further, the population size in each community is normalized by N .

As preliminary results, we first provide the results for case A using the data provided (cf. Fig.

5.11(a)

). Fig. 5.11(a) shows the evolution of number of devices normalized by N in the three active (S, I, R) states. Let S total = i∈C S i /N , I total = i∈C I i /N and R total = i∈C R i /N . Initially, when there are many devices without information, the devices with information are able to send the information to them. Thus, dI/dt is high and more devices change their state from S to I.

However, as time increases, the fraction of devices in state S decreases as most of devices now have the information. This reduces dI/dt. From Fig. 5.11(a) it can be seen that initially dI/dt is very high. However, it becomes equal to 0 for some time and then again increases. This is due to the mobility pattern of the users and the community structure. Consider some communities where there are devices in state I and the devices are not moving out of the community. Also consider all devices in other communities to be in state S. When all the devices in the communities with devices in state I are in state I, there are no devices in state S in those communities and thus dI/dt = 0.

However, when the devices in state I move to another communities where there were no devices in state I, they are able to meet devices in state S. This again increases dI/dt. Fig. 5.11(b) shows the evolution of S i , I i and R i for community numbered one and three. Due to the difference in the number of devices in steady state of the mobility, the curves for two considered communities differ.

As we add latent states to case A, we next show the evolution of number of devices in S, I and R states normalized by N when latent states are added, case B. We then bring out the differences in the fraction of devices in S, I and R. Fig. 5.12(a) shows the evolution of the fraction of devices in states S, I and R for the case A and case B. We call the devices in states S, I and R for the case when latent states are added as active devices. Let S total,active = i∈C S i /N , I total,active = i∈C I i /N and R total,active = i∈C R i /N . The maximum difference between the fraction of devices in state I for the two cases at any time is found to be ≈ 0.23186, i.e., max{I total -I total,active } ≈ 0.23186.

However, this is not a correct measure as there is a population difference in the three active states because of the addition of the latent states. We thus normalize the population in the active states by S total,active +I total,active +R total,active . When the results are normalized, the max{I total -I total,active } at any time reduces to ≈ 0.043694 (cf. Fig. 5.12(b)). We then plot S total -S total,active , I total - I total,active and R total -R total,active on the actual population scale (cf. Fig. 5.12(c)) as another representation for Fig. 5.12(b). It can be seen that even a small difference of ≈ 0.04369, on the actual population scale can be of high significance. This difference is ≈ 685440 on the actual population scale.

Using case B ′ we next show how beamforming can effect the dissemination process. We first present the comparison of the number of devices in states S, I or R when normalized by the active population for case B and case B ′ . We set the percentage of devices that are beamforming in a community as x = 6% (cf. Fig. 5.13(a)). Let x = 0% be the case B. Fig. 5.13(a) shows that the max{I total,x=6% -I total,x=0% } ≈ 0.1792. This difference in the actual population scale is ≈ 281240 (cf. Fig. 5.13(b)). The difference in the curves of I for the two cases clearly suggests that beamforming2 can provide better results in terms of more devices receiving information quickly when x = 6%. We then investigate the effect of x on the dissemination process. As suggested in [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF], the number of long links decreases the average path length and hence more number of devices are able to receive information in less time, i.e., faster dissemination is achieved, similar results for this case is also obtained. We plot I total,x=y% -I total,x=0% , where y ∈ 2, 6, 10 (cf. Fig. 5.13(c)). Note that when x = 2% there are less number of devices that beamform and hence the curve takes off slowly when compared to when x = 10%. This proves that the information dissemination is enhanced in terms of number of devices receiving information over time. All the above results are generated considering the case when only one community, one eN B, initially has the source of information. However, in realistic scenarios, different public warning messages could originate in many different eN Bs. Let two public warning message be generated in 2 communities (1 and 2) that are far apart. Here, we show the evolution of the number of devices in the active states normalized by N . Here we consider devices in state I as the devices that have received at least one public warning message. We then plot the difference in the fraction of devices in different active states on the actual population scale (cf. suggest that more devices have at least one message with them.

Further, all the above results are obtained using M P c generated through G c . Let for the two cases (when M P c is used and when M P v is used), the total number of devices in the three active states normalized by total number of devices in active state be termed as S total,y , I total,y and R total,y where y ∈ M P c , M P v . When M P v is used, different results in terms of number of devices in state I are obtained 3 (cf. Fig. 5.15). This is because now the movement of the device is only restricted to neighboring community and there are no long jumps as in the case when M P c was used. However, it is observed that some time communities far apart also start disseminating information. Consider two communities i and j more than one hop away. Assume that community i have devices in state I initially. Over time, these devices from community i move to other neighboring communities. Now suppose that a device in state E I has moved and remained in state E I until it reached community j. On reaching community j the device switches to state I and start disseminating the information.

The same phenomenon is observed in the obtained results 3 . As discussed before constraining the mobility affects the dissemination process, the same phenomenon is observed in the case when M P v is used, (cf. Fig. 5.15). It can be noted that there is a high difference in the devices in state I for the two cases.

We now show results obtained using the mobility model when return rates are associated. Towards this, we first show the difference in the fraction of active devices in states S, I and R when different mobility models are used with the addition of latent states and beamforming. Let the mobility model when return rates are used be called as mobility2 and mobility model when return rates are not used be called as mobility1. Here we show the difference in the fraction of active devices for the two cases. As return rates are included, a device in state I will return back to its community where the dissemination process has already been started and the fraction of devices not having the information will be low. This lowers dI i /dt. When compared to when mobility1 is used, the I mobility1,total -I mobility2,total is large. Fig. 5.16 shows the same. We then show the change in fraction of devices in the three active states when beamforming is used and when beamforming is not used on the mobility2. The percentage number of devices beamforming in a community are set to x = 6%. Note that when there is no beamforming x = 0%. As discussed previously that beamforming enhances information dissemination, same phenomenon was observed in the case of mobility2 also (cf. Fig. 5.17). S total,x =6% -S total,x =0% I total,x =6% -I total,x =0% R total,x =6% -R total,x =0% Figure 5.17: Evolution of differences in number of devices in the three active states. The difference is calculated between the case when x = 6% and x = 0% for the mobility model with return rate.

Conclusion

In this Chapter, we present a model that could help in enhancing the information dissemination in terms of the fraction of devices having the information across the population in a D2D based communication network. We combine the concepts of epidemic model, beamforming and metapopulation to build our model. We use the data provided by the D4D organizers to determine the movement rates for the movement of the devices from one community to another. To realize the information dissemination process we use SIR type epidemic model with addition of latent states E S , E I and E R . We then add beamforming on the above proposed variation of the SIR model.

Through the results, we show that by allowing small fraction of devices to beamform, dissemination process can be enhanced in terms of devices having information in the environment where the density of active devices is constantly changing. Thus, this Chapter presents three main contributions, first the design of the two models: a human mobility model for which we study the steady state limit and the transient behavior of an information dissemination model under the mean field assumption.

Secondly, we introduced the latent states to account for variable density and finally, we showed how beamforming and mobility in a network with community structure could be applied to achieve large scale dissemination in a dynamic D2D based communication network.

CHAPTER6

Conclusion

The evolution of wireless networks and the need for providing self organizational capabilities to wireless devices for achieving better performance has lead us to propose algorithms in Chapters 3, 4 and 5. Better performance in wireless networks is achieved via reduction in average path length, increase in connectivity and how quickly information is disseminated in the network. The algorithms are designed such that they operate in a decentralized manner, use only locally available information, concepts from self organization such as Lateral Inhibition and Flocking, human mobility, stability, beamforming and dynamic density.

In Chapter 3 we investigate how small world properties can be efficiently achieved in static wireless networks in an autonomous environment by using concepts from self organization such as Lateral Inhibition and Flocking analogy. We also use the concept of beamforming to achieve the goals. The algorithm works using locally available information and does not require the knowledge of the whole network. Lateral Inhibition is used to form virtual communities within the network for reducing message complexity while the Flocking analogy is used to determine beam properties.

Results show that, high performance can be achieved not only in terms of reduced AP L but also in terms of connectivity. Reduced AP L relates to smaller number of hops from one node to another.

Hence, the transmission of information from a source node to the destination node requires less time.

However, due to limitations of the algorithm developed in Chapter 3, it is not applicable to mobile networks. Mobility creates diversities and clusters, and causes changes in the network structure.

When mobility is associated, interactions between devices are intermittent. However, there is some percentage of certainty in the interactions. With respect to all the interactions a device had, we call the percentage certainty as stability. Using this definition of stability, we define an algorithm 139 in Chapter 4 that achieves better results in terms of dissemination. In Chapter 4 we propose a probabilistic approach to compute the stability of a node in a mobile environment. The algorithm uses beamforming to achieve the goal of faster dissemination of information in the network and operates using only locally available information. Beamforming is performed by devices in the network that have low stability and in the direction of high stability devices. In this Chapter, faster dissemination relates to how quickly large number of devices are able to receive the information flowing in the network. In this Chapter, it is also discussed that the proposed algorithm shows better results over other related studies. Further, the effect of the variation of the related parameters on the information dissemination is also clearly presented.

The algorithm in Chapter 4, however, does not consider the scenario when the density in mobile network is changing with time. Thus in order to incorporate dynamic density scenario, in Chapter 5 we define three latent states where the devices in the latent states do not participate towards disseminating information. We consider SIR type dissemination model and relate each state in SIR model with a latent state. The set of devices that are in S, I or R states are only considered in relation to the dissemination process. The transitions between active states and latent states happen with a certain rate. In order to achieve quicker dissemination, mobility is combined with beamforming on top of the dissemination process described by the updated SIR model. The results show that the process of dissemination in dynamic density scenarios can also be enhanced in terms of more number of devices being able to receive information in less time.

In all the three contributions, the number of beamforming devices are limited. In Chapter 3, Lateral Inhibition and Flocking alignment rule is used to identify the beamforming devices while in Chapter 4 low stability devices were allowed to beamform. In Chapter 5 the number of beamforming devices was set to a low value. Limiting the number of beamforming devices allows the small world phenomenon to occur as discussed in [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF].

Future Directions

The algorithms proposed in this thesis provide a way to enhance information dissemination in an autonomous environment. The scenarios in which our algorithm is useful include spreading of public warning messages across the population efficiently. Enhancing information dissemination process helps in obtaining quicker relief in a disaster hit scenario. Another, scenario where the proposed algorithms can be useful include, dissemination of traffic updates over a mobile network. The D2D communication use-case currently shows the necessity of efficient dissemination of public warning message system. We think that our algorithms can bridge this gap.

In an autonomous environment, the decision of devices to beamform using local interactions where global favorable results are achieved can be studied using game theory. Thus, as a possible extension of the present work, game theoretic approach can be applied and studied to achieve the goals. In a game theoretic approach, the decision to beamform is a game that is played by the device. Whether to cooperate with other devices and whether changing the beam property can help in achieving global results, are some of the questions that can be interesting to research on. Towards this, one possible extension will be the application of evolutionary game theory to achieve the goals.

In Chapter 5, we have not used changes in the population size, i.e., addition of new devices and removal of old devices. This, in a communication environment can be explained through many ways.

For example, due to hardware failures, change in technology and growing needs for the devices, to name a few. Addition of such concept would add more realism to our model. In order to model such processes, there is a need for the knowledge about the rates at which the devices are added or removed from the network. Capturing such information in CDRs could help in enhancing the model and will introduce more realism towards the study of the dissemination process. Also to model more realistic scenarios, we suggest the use of probability of connection in the given direction for the calculation of k [START_REF] Bettstetter | On the Connectivity of Ad Hoc Networks[END_REF].

The mobility characteristics used in this dissertation are obtained from the analysis of the sampled human mobility data. In Chapter 4, the mobility characteristics used are based on the mobility patterns observed for the data collected in the region of USA. However, in Chapter 5 we use the mobility characteristics that are derived from samples collected over the region of Ivory Coast. In both Chapters, due to the use of CDR, mobility can only be approximated. The sampling of the mobility data should be conclusive and extensive to exactly map human mobility pattern. The above requirements would lead to large number of samples extracted at a very high rate and would require efficient data storage mechanisms.

Applications studying human mobility are diverse and range from studying traffic flows, cascad-ing behaviors, road/rail network planning, understanding urban developments (growth of spatial networks like roads and railways [START_REF] Louf | Emergence of Hierarchy in Cost-Driven Growth of Spatial Networks[END_REF]), epidemic control and outbreaks, evolution of networks etc.

The study of such applications is only possible if the data collected on human mobility is conclusive and has both timing and behavioral aspect. The study of such applications is hampered if the sampled data is a CDR. In CDR a tuple is only created when a call is made and not when the location is changed. Thus, mobility can only be approximated using CDR. If the above mentioned applications are considered, CDR needs to be replaced with more active entries of the mobility information. If such active datasets on human mobility are made available, better understanding of human mobility can be achieved and the above mentioned applications can be made more robust.

Considering individuals with autonomous behavior, the datasets collected thus far have failed to record any behavioral aspect attached to human mobility. Researchers cite security issues towards having such kind of information in the dataset. However, if such information were to be made available, mobility models could be made more subtle. Using such models will surely enhance the algorithms proposed in Chapter 4 and 5. The lack of such dataset and efficient storage of dataset enables us to propose another future direction whereby mobility datasets could be made more comprehensive and manageable.

APPENDIXA

A Self-Organization Framework for Wireless Ad hoc Networks as Small World This Appendix provides detailed description of algorithm proposed in [START_REF] Banerjee | A Self-Organization Framework for Wireless Ad Hoc Networks as Small Worlds[END_REF]. In this Appendix, we propose a distributed algorithm for small world creation that achieves path length reduction while maintaining connectivity. In this Appendix, we first define a new centrality measure that estimates the structural importance of nodes based on traffic flows in the network, which is used to identify the set of nodes that beamform. We show, using simulations, that this leads to significant reduction in path length while maintaining connectivity.

Central to the design is a new measure of centrality defined in this Appendix that allows distributed estimation of the structural importance of nodes in the network. We define Wireless Flow Betweenness (W F B) which gives an accurate estimate of the Flow Betweenness Centrality (F BC) [START_REF] Freeman | Centrality in Valued Graphs: A Measure of Betweenness Based on Network Flow[END_REF]. The proposed measure enhances the earlier measure defined in [START_REF] Banerjee | Self-Organization of Wireless Ad Hoc Networks as Small Worlds using Long Range Directional Beams[END_REF] by identifying key redundancies. The key aspect of W F B is that it can be computed in a completely distributed manner by exploiting the wireless broadcast advantage (W BA) [START_REF] Wieselthier | Energy-Efficient Broadcast and Multicast Trees in Wireless Networks[END_REF] for information regarding traffic flow, thereby incurring negligible overheads.

The rest of the Appendix is organized as follows. Section A.1 introduces W F B after the introduction of table of notations used. A centralized scheme for choosing beamforming nodes is shown to give promising results for small world creation. Subsequently, a distributed algorithm for small world creation using beamforming is proposed and evaluated using simulations in Section A. For the problem of distributed self-organization of the network, there is a need for nodes to accurately estimate their importance with respect to paths in the network. This constraint makes it unsuitable to use any of the conventional measures as they consider a centralized view of the network. In addition to the distributed computation of the centrality itself, nodes need to decide on their beamforming behavior based on these values. As nodes with high betweenness are ideal for shortcut creation, nodes need to estimate the rank of their betweenness in the network. In order to satisfy these requirements, the algorithm design in this Appendix is centered on a new measure of centrality that allows nodes to decide on shortcut creation depending on the structure of the network.

the neighborhood of v, would be non-trivial and costly. Instead, we propose to estimate the betweenness of a node by propagating network information as part of traffic flows which uses recursive computation at nodes to obtain an accurate estimate.

The betweenness of a node v based on the set of traffic flows in the network, was defined in [START_REF] Freeman | Centrality in Valued Graphs: A Measure of Betweenness Based on Network Flow[END_REF] as the F BC which refers to the share of the maximum flow between all node pairs in the network that passes through v. However, F BC requires nodes to maintain global network state. Many other proposed measures of centrality for wireless ad hoc networks [START_REF] Maglaras | New Measures for Characterizing the Significance of Nnodes in Wireless Ad hoc Networks via Localized Path-based Neighborhood Analysis[END_REF] requires knowledge of multi-hop neighborhood of a node, which is again costly in terms of transmission overheads. In order to minimize the state information, the approach centers around estimation of the number of flows by each node using neighborhood values of centrality.

For any node u, the number of transmissions it is aware of is obtained as g(u) w(u) . Thus, a node v can gain an estimate of the number of transmissions in the network using the above estimation for each of its neighbors u ∈ N (v). Nodes piggyback their self-computed values of centrality whenever they transmit a packet, either as a forwarding node or as source. However, this involves multiple redundancies that can result in inaccurate estimation.

The first redundancy arises due to the term g(u) that gives the number of packets transmitted by a node u, which lies in the neighborhood of v. As v can overhear all of u transmissions, it counts all of these as part of the number of traffic flows g(v) it counts in its neighborhood and uses to compute w(v). Thus, g(v) ≥ g(u)∀u ∈ N (v). As g(u) is counted again as part of the expression g(u) w(u) , this results in overestimation. Thus, node v needs to ensure that the term g(u) is not counted multiple times so as to accurately estimate the number of traffic flows which u is aware of but v is not. Therefore, the estimated number of additional flows that u is aware of is given as

a f (u) = g(u) w(u) -g(u). (A.1.2)
The betweenness of v can be computed using the a f values of all its neighbors as

w(v) = g(v) o(v) + u∈N (v) a f (u)
.

where o(v) denotes the number of traffic flows overheard by v, including those transmitted by v itself. A node updates its betweenness if it either transmits a packet or overhears one from its neighbors. into consideration the number of flows overheard by u as well as the node with maximum forwarding count in N (u). The consideration of the neighbor with maximum forwarding count implies that a majority of flows are always accounted for in a neighborhood, thereby minimizing the probability of flows not being counted. It can be noted that this estimation over successive hops can stop when a node itself has the maximum forwarding count in its neighborhood, leading to an estimation error.

On further consideration, however, it is observed that this is unlikely to occur unless the node is the global maxima, i.e. has the maximum centrality value in the entire network. Thus, the possibility of inaccuracies in estimation is minimized. This is verified in the next Section based on the rank correlation of W F B values in the network with that of centrally computed F BC.

A.1.2 Correlation with F BC

To verify the validity of the proposed W F B measure,we compare the values obtained with the F BC.

Since the relative importance of a node with respect to either betweenness measure is given by its nodes with high values of W F B as beamforming nodes. The issue of distributed identification of beamforming nodes is discussed later. Instead, it is considered that somehow the top ranking nodes with respect to W F B values are identified and create beams. Based on the insights obtained in this Section, we formulate an algorithm for distributed beamforming in the next Section.

We consider that the top 10% (i.e. p = 0.1) of all nodes in the network create directional beams using sector model. Let r be the omnidirectional range and B w be the beam width. The optimal beam width, B * w , used is calculated

B * w = arg max Bw r 2π B w p nf p nl . (A.1.5)
where p nf and p nl are the probabilities that at least one node is located in the first and last sectoral regions. Note that, we assume the path loss exponent to be equal to 2 and free space propagation. The choice of the two probability terms is dictated by the motivation of maintaining connectivity while maximizing beam length. Since an accurate estimate of maintaining bidirectional connectivity would require knowledge of the entire network, we use the term p nf to estimate the probability that connectivity is maintained with the omnidirectional neighborhood. As the first region under the beam lies within the omnidirectional range, a higher number of nodes here increases the probability that omnidirectional neighbors can be reached. Increasing the beam length, however, We show the performance improvements available for increasing size of the network region, indicated using D as the maximum distance between any two nodes. For d = 3, a relatively higher fraction of node pairs are connected unidirectionally, though this is still lower than the value for randomized beamforming. The improvement in connectivity results from the fact that nodes with high value of centrality are better connected. For lower node density, the higher fraction of unidirectional connectivity results due to the choice of beamforming nodes.

Nodes with high values of W F B are likely to be neighbors of each other as they are located towards the center of the network. As nodes with high values of W F B are chosen as the beamforming nodes, they are likely to be neighbors to each other. In the case of lower node densities, this results in a higher fraction of neighboring nodes which are beamforming thereby resulting in unidirectional connectivity. This is alleviated for higher node densities as, in spite of neighboring nodes creating beams, a higher number of neighbors continues to use omnidirectional beams thereby increasing the chances of bidirectional paths. A.2 Distributed Small World Creation using W F B

We now focus on distributed algorithm design for small world creation using directional beamforming. The design centers around nodes determining their beamforming behavior based on their estimated importance in the network, thereby adapting small world creation to the network structure. Specifically, the beamforming behavior of a node is determined based on the relation between its W F B value and those of its neighbors. This is shown to result in significant reduction in average path length accompanied by negligible loss in connectivity, thereby realizing small world properties.

In the previous Section, we illustrated the benefits achievable by using top ranked nodes by W F B as beamforming nodes. However, as the set of nodes with highest values of W F B was identified using global network information, it is not suitable for distributed implementation. Further, as discussed before, only choosing nodes with high values of W F B can result in unidirectional connectivity at low node densities.

A.2.1 Distributed Beamforming Algorithm

The As nodes broadcast their W F B values as part of packet transmissions, all nodes are aware of the values of their neighbors. As part of the algorithm, a node v decides on using a directional beam if its own value exceeds that of its neighbors by a similarity factor β. Thus, the beamforming condition for a node v can be expressed as

w(v) w avg (N (v)) > β (A.2.1)
where w avg (N (v)) denotes the average W F B for v's neighborhood. The above condition ensures that only nodes with high values of W F B choose themselves for beamforming. The fraction of such nodes is determined by β. A higher value of β implies a stricter condition resulting in fewer beamforming nodes. Further, the condition also results in a lower chance of neighboring nodes creating beams. This is because, a node is chosen if its value exceeds those of its neighbors by the similarity factor β, the condition is unlikely to hold true for any of the neighbors themselves, and therefore excludes them from beamforming. The choice of beam width and beam direction is the same as for centralized choice of beamforming nodes.

The set of nodes that decide on using directional beams is illustrated in the distributed choice of nodes are relatively more spread out, thereby reducing the set of neighbors that simultaneously use beams resulting in better connectivity.

A.2.2 Simulation Results

We evaluate the proposed algorithm using simulations at different node densities as earlier. The value of β is chosen such that the fraction of beamforming nodes stays close to p = 0.

A.3 Conclusion

In this Appendix, we explored the use of directional beamforming for self-organization of a dense wireless ad hoc network as a small world and provided a simulation based analysis of the achievable performance benefits of randomized beamforming and identify the challenges involved. Subsequently, a detailed distributed algorithm for nodes to decide on their beamforming behavior was provided with a new measure of betweenness centrality, Wireless Flow Betweenness (W F B), which is used to identify beamforming nodes. Using simulation results it was shown that significant performance benefits can be achieved over randomized beamforming.

APPENDIXB

SET3 Details

The SET3 is a coarse grain dataset containing billion records which is sub divided into 10 small sub datasets each consisting of mobility patterns for two weeks. Table B.1 shows the start and end time for the sub datasets of SET3. The mobility patterns are generated after concatenating these sub datasets. Each entry in the sub dataset has been made when a user makes a call and consists of fields like associated subprefecture ID, user coordinates and time when the call was made. Such kind of entry makes SET3 a Call Detail Record (CDR) dataset. As stated in Chapter 5, due to the information pertaining to users, we are able to generate the density of the users over each sub dataset (cf. ). The asymmetrical nature of the movement rate matrices relates to the fact that first, users are not tracked continuously, second, the dataset is a CDR with a possibility of user making a call mainly from certain locations, third, the number of user going from subprefecture i to subprefecture j could be different from the number of those going from j to i.

As SET3 is related to the mobility of the users it is essential to determine the mobility parameters associated to the data. We thus determine the distribution of jump length and radius of gyration for the user. Similar to the definitions in Section 5.2.2, consider a user u from the dataset. Let subprefecture entry for each entry for u form a set U such that U = (u 1 , u 2 , . . . , u n ) where u i is the subprefecture entry. The jump length is calculated as the euclidian distance between two consecutive entries, i.e., jump length= (u i (x)u i-1 (x)) 2 + (u i (y)u i-1 (y)) 2 . The radius of gyration, r g , is calculated as the root mean square distance of the jump length from the mean jump length. Consider X be the set of jump length samples. The mean jump length is defined by x =  Cependant, dans les réseaux réels, les changements de structure ne sont pas dus qu'à la mobilité, mais également à des changements de la densité des noeuds à un moment donné. Pour tenir compte de l'influence de tels événements sur la diffusion des informations concernant la sécurité publique, l'auteur utilise les concepts de modèle de métapopulation, épidémiologiques, "beamforming" et mobilité géographique obtenu à partir de données D4D. L'auteur propose la création de trois états latents qu'il ajoute au modèle épidémiologique connu: SIR. L'auteur étudie les états transitoires en analysant l'évolution du nombre de postes ayant reçu les informations et compare les résultats concernant ce nombre dans les différents cas. L'auteur démontre ainsi que le scenario qu'il propose permet d'améliorer le processus de diffusion des informations. Il montre aussi les effets de différents paramètres comme le nombre de sources, le nombre de paquets, les paramètres de mobilité et ceux qui caractérisent les antennes sur la diffusion des informations.

C.1 Introduction

Compte tenu des progrès technologiques récents et de la croissance des besoins humains, le déploiement des réseaux sans-fils a attiré récemment beaucoup d'attention. Beaucoup de propriétés qui concernent les performances des réseaux sans-fil ont été identifiées. [START_REF] Andrews | A Primer on Spatial Modeling and Analysis in Wireless Networks[END_REF] Puis, beaucoup d'études se sont concentrées sur les moyens de résoudre les problèmes de scalabilité, les problèmes de supervision et ceux qui sont introduits par les développements technologiques. D'immenses périls topologiques dans le déploiement des réseaux sans fils ont rendu difficiles pour les hommes de contrôler les besoins des réseaux sans-fils en termes d'énergie et de développement technologiques. [START_REF] Dressler | A survey on Bio-Inspired Networking[END_REF]. Il faut prendre en compte les limites dues aux problèmes cités précédemment mais aussi de nombreux autres facteurs comme les contraintes réseaux, les interactions avec l'environnement, l'utilisation des ressources, le développement de différents types d'architectures hétérogènes. [START_REF] Dressler | A survey on Bio-Inspired Networking[END_REF]. L'évolution des réseaux sans-fil ad hoc rend difficile pour les algorithmes existants de répondre au sujet de beaucoup de détails qui leur sont associés comme l'accroissement de la concurrence et des collision qui conduisent à rechercher des algorithmes qui donnent de bons résultats dans des auto * environnements1 . La croissance des réseaux a amené les chercheurs à considérer des systèmes complexes, distribués et adaptatifs qui puissent répondre à la plupart de ces questions et croitre avec le réseau.

Pour qu'un système soit auto-organisé il faut qu'il réponde à quatre paradigmes synthétisés dans [START_REF] Prehofer | Self-Organization in Communication Networks: Principles and Design Paradigms[END_REF]. Il faut que les entités du système fonctionnent de manière autonome en utilisant des informations locales, soient très synchrones, aient une mémoire de faible durée de vie (historique court) et s'adaptent aux changements de l'environnement. Il est difficile d'avoir de bonnes performances globales en utilisant seulement des informations locales dans un environnement distribué. Si on considère la Nature, elle résout très efficacement la plupart des problèmes complexes en utilisant des règles très simples et en suivant les quatre paradigmes de [START_REF] Prehofer | Self-Organization in Communication Networks: Principles and Design Paradigms[END_REF]. L'application des phénomènes naturels en informatique remonte à l'époque de Sir Allan Turing, où il a modélisé les dessins sur la peau d'un animal en utilisant des règles simples. Sa recherche a largement ouvert un champ pour que les chercheurs étudient l'utilisation de phénomènes naturels dans leurs domaines de recherche respectifs. Dans les cas réels, cependant, quelques chercheurs ont soutenu que la nature de la loi puissance tronquée est une estimation provenant de l'échantillonnage des données [START_REF] Mossa | Truncation of Power Law Behavior in Scale-Free Network Models due to Information Filtering[END_REF] et dépend de la région dans laquelle les échantillons sont prélevés [START_REF] Csáji | Exploring the Mobility of Mobile Phone Users[END_REF]. Dans [START_REF] González | Understanding Individual Human Mobility Patterns[END_REF] les données sur la mobilité proviennent des Etats Unis alors que dans un travail récent [START_REF] Csáji | Exploring the Mobility of Mobile Phone Users[END_REF] les échantillons provenaient du Portugal. [START_REF] Lawrence | The Making of a Fly: The Genetics of Animal Design[END_REF][START_REF] Nagpal | An Algorithm for Group Formation in an Amorphous Computer[END_REF][START_REF] Nagpal | Engineering Amorphous Computing Systems[END_REF][START_REF] Afek | A Biological Solution to a Fundamental Distributed Computing Problem[END_REF] et la migration en groupe [START_REF] Reynolds | Flocks, Herds and Schools: A Distributed Behavioral Model[END_REF]. Il utilise aussi le concept de centralité afin de construire la solution.

C.1.1 Les Défis

L'auteur utilise l'inhibition latérale pour créer de petites régions logiques dans un réseau statique. de [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Maiti | Epidemic Broadcasting in DTNs using Directional Antenna[END_REF][START_REF] Maiti | Analyzing the Performance of Epidemic Broadcasting in DTNs using Directional Antenna[END_REF]. Toutefois la seule différence entre [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Maiti | Epidemic Broadcasting in DTNs using Directional Antenna[END_REF][START_REF] Maiti | Analyzing the Performance of Epidemic Broadcasting in DTNs using Directional Antenna[END_REF] et [START_REF] Li | Collaborative Vehicular Content Dissemination with Directional Antennas[END_REF] concernait la sélection des machines qui "beamform". Au contraire de [START_REF] Peruani | Modeling Broadcasting using Omnidirectional and Directional Antenna in Delay Tolerant Networks as an Epidemic Dynamics[END_REF][START_REF] Maiti | Epidemic Broadcasting in DTNs using Directional Antenna[END_REF][START_REF] Maiti | Analyzing the Performance of Epidemic Broadcasting in DTNs using Directional Antenna[END_REF], où la direction du faisceau et le choix des noeuds qui créent un faisceau était aléatoire, l'auteur pense que si le choix de ces noeuds est basé sur une mesure et si les faisceaux sont dirigés dans une direction où il y a plus de noeuds qui n'ont pas reçu les informations, le processus de diffusion peut être amélioré.

Dans ce contexte, la première question à laquelle il faut répondre est: "quel noeud doit créer un faisceau?" Après avoir fait ce choix, il faut choisir la direction du faisceau. Dans la section C. Comme nous nous intéressons à la diffusion des informations dans une région de grande échelle, l'approximation du champ moyen est le modèle qui convient le mieux pour modéliser la diffusion dans le réseau des contacts à travers le pays. Le processus de diffusion des informations a été considéré comme très proche d'un processus de diffusion d'une épidémie à travers une population pour lequel le modèle SIR existe. On peut trouver une synthèse sur les modèles épidémiologiques dans [START_REF] Hethcote | The Mathematics of Infectious Diseases[END_REF][START_REF] Britton | Stochastic Epidemic Models: A Survey[END_REF].

Dans un modèle obtenu par une méthode de champ moyen, les états, S, I et R correspondent respectivement aux noeuds n'ayant pas de paquet, aux noeuds ayant un paquet et étant prêt à le transmettre, et aux noeuds qui ne participent plus à la diffusion des informations afin d'économiser l'énergie. Dans ce contexte il a été montré que la diffusion des informations est influencée par beaucoup de facteurs tels que: les communautés dans le réseau, les rafales [START_REF] Karsai | Small but Slow World: How Network Topology and Burstiness Slow Down Spreading[END_REF], la force de la connexion [START_REF] Miritello | Dynamical Strength of Social Ties in Information Spreading[END_REF], la source de l'infection, le nombre de noeuds infectés, les paramètres de la mobilité humaine (section C.3), les lieux les plus visités, [START_REF] Wang | Safety-Information-Driven Human Mobility Patterns with Metapopulation Epidemic Dynamics[END_REF], la structure du réseau [START_REF] Nicosia | Impact of Network Structure on a Model of Diffusion and Competitive Interaction[END_REF], le type d'activité [START_REF] Vazquez | Impact of Non-Poissonian Activity Patterns on Spreading Processes[END_REF], les caractéristiques des machines [START_REF] Wang | Information Spreading in Context[END_REF] et dans la section C.3, l'altruisme [START_REF] Hui | Selfishness, Altruism and Message Spreading in Mobile Social Networks[END_REF], et les mesures sociales [START_REF] Keeling | Networks and Epidemic Models[END_REF]. Cependant, comme l'a fait remarquer [START_REF] Kivelä | Multiscale Analysis of Spreading in a Large Communication Network[END_REF], les caractéristiques de la mobilité humaine sont les paramètres qui ont le plus d'importance, si on les compare aux autres.

Pour un modèle à l'échelle d'un pays, l'auteur a utilisé les données fournies par les organisateurs d'une étude de D4D (Data for Development) et par Orange Labs [START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF]. L'analyse des données révèle que dans une grande population, il existe des communautés et que la densité de la population évolue en fonction du temps. Une telle structuration d'une grande population en communautés où les interactions entre les communautés sont dues à la mobilité, a déjà été étudiée en créant un modèle synthétique de population appelé métapopulation [START_REF] Watts | Multiscale, Resurgent Epidemics in a Hierarchical Metapopulation Model[END_REF][START_REF] Arino | Disease Spread in Metapopulation[END_REF] où il a été dit que l'existence des communautés dans une grande population est une évidence et qu'elles influent sur le processus de diffusion. Si une personne était réduite à rester dans une communauté, elle ne pourrait pas se déplacer librement. Par exemple, le mouvement d'une personne d'un pays à un autre est restreint par les douaniers. Ceci entrave la diffusion des épidémies. La Figure C.3 montre la différence entre le nombre de personnes infectées quand il y a c communautés et quand il n'y en a qu'une. Au début, la grande différence entre les courbes est due au fait que plus de personnes en ont rencontré d'autres quand elles ne sont pas contraintes à rester dans une communauté donnée et ainsi la diffusion est rapide. Récemment, il a été montré dans [START_REF] Lund | Effects of City-Size Heterogeneity on Epidemic Spreading in a Metapopulation: A Reaction-Diffusion Approach[END_REF] que non seulement la structure de la communauté influe sur le processus de diffusion mais que la densité des communautés a aussi une grande influence.

Dans les réseaux de communication, cependant, on peut rencontrer des densités dynamiques dans deux cas: premier cas: processus de naissance et de mort, deuxième cas: processus de sommeil et de veille (cas qui a éte peu cité dans la littérature). Ainsi dans un réseau D2D où la structure du réseau dépend aussi de la mobilité humaine et des caractéristiques des machines, l'auteur cherche Dans la section C.3 l'auteur utilise une approche probabiliste pour calculer la stabilité d'un noeud en environnement mobile. L'algorithme utilise aussi du "beamforming" dans le but d'accélérer la diffusion des informations dans le réseau. Il fonctionne en n'utilisant que des informations locales.

Le "beamforming" est utilisé par les noeuds qui ont une faible stabilité en direction des noeuds qui ont une forte stabilité. Dans cette section l'accélération de la diffusion signifie que plus de noeuds sont capables de recevoir les informations circulant dans le réseau, plus vite. Il est aussi montré dans cette section que l'algorithme proposé donne aussi de meilleurs résultats pour différents cas et les effets sur la diffusion de l'informations des variations des paramètres du réseau sont analysés. Toutefois l'algorithme de la section C.3, ne considère pas le cas où la densité dans les réseaux mobiles évolue au cours du temps. L'auteur, afin de tenir compte des cas de réseaux à densité dynamique, introduit trois états latents,. Les noeuds dans l'un des états latent ne participent pas à la diffusion dans la section C.4. L'auteur considère un modèle de diffusion de type SIR et relie chaque état dans le modèle SIR à un état latent. Seuls les noeuds qui sont dans les états S, I ou R participent au processus de diffusion. Les transitions entre les états actifs et les états latents se produisent avec un taux donné. Pour accélérer la diffusion la mobilité est combinée avec le "beamforming" au dessus du processus de diffusion décrit par le modèle enrichi des états SIR. Les résultats montrent que le processus de diffusion des informations dans le cas d'un réseau à densité dynamique peut aussi être amélioré: plus de noeuds reçoivent les informations en moins de temps.

Dans chacune des trois contributions l'auteur propose que les algorithmes limitent le nombre de noeuds qui créent des faisceaux. Dans la section C.2, l' inhibition latérale est utilisée pour limiter le nombre de noeuds qui créent un faisceau alors que dans la section C.3 seuls les noeuds de faible stabilité sont autorisés à le faire. Dans la section C.4 le nombre de noeuds qui créent un faisceau est fixé à une valeur faible. Le fait de limiter ce nombre de noeuds permet au phénomène des "small world" de se produire comme cela a été analysé dans [START_REF] Watts | Collective Dynamics of Small World Networks[END_REF].

C.6 Directions Futures

Les algorithmes proposés par l'auteur fournissent une méthode pour améliorer la diffusion des informations dans un environnement autonome. Elle pourrait aider à diffuser efficacement des messages d'alertes dans la population dans n'importe quelle sorte de réseau (statique ou mobile). Un cas d'application de communication D2D concerne la nécessité de diffuser efficacement les messages d'alertes. Utiliser les trois algorithmes proposés avec les environnements et règles du D2D serait évidemment utile. Les algorithmes proposés peuvent aussi être utiles dans différents cas de problèmes de diffusion.

Cependant, des extensions des algorithmes proposés peuvent être prévues. La décision pour un noeud de créer un faisceau est une décision autonome où en utilisant les interactions locales on peut vouloir obtenir des améliorations globales. En théorie des jeux, la décision pour les noeuds de créer un faisceau est un jeu joué par les noeuds. Ici voici quelques questions dont les noeuds aimeraient connaître la réponse: les questions comme celle de savoir si pour le noeud une coopération avec d'autres noeuds ou celle de savoir si un changement des propriétés du faisceau améliorerait les résultats globaux. Dans cette direction, l'application de la théorie des jeux évolutionnaires pourrait être étudiée.

De plus, dans la section C.4, l'auteur n'a pas utilisé un modèle markovien de processus de naissance et de mort avec des additions de nouvelles machines et la suppression de vieilles machines.

2. 1

 1 Comparison between various research articles dealing with beamforming and connectivity. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1 Comparison between various researches related to achieving Small World characteristics in wireless networks. More details on Abhik et al. algorithm [1] are provided in appendix A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Notations and their meaning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Notations and their meaning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.2 Beamforming strategies. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.3 Factors affecting the dissemination of packet. The table shows the effect on the time taken to disseminate the information in the network completely when the parameter value increases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 Notations and their meaning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Notations and their meaning. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B.1 Start and End time for fragments of SET3. . . . . . . . . . . . . . . . . . . . . . . . xi List of Figures 2.1 Source: [2], (a) regular graph with p = 0, (b) small world graph with 0 < p < 1 where some of the edges from (a) were rewired, (c) random graph with p = 1 where complete rewiring of edges in graph (a) were performed. . . . . . . . . . . . . . . . . . . . . . 13 2.2 (a) regular graph with p = 0, (b) small world graph with 0 < p < 1 where edges were added to few nodes in (a), (c) random graph with p = 1 where edges were added to all the nodes in (a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 The connectivity and temporal distance in the time varying graph. . . . . . . . . . . 18 2.4 Gain pattern obtained for different B b and M = 8 when using U LA model. . . . . . 23 2.5 Depiction of three Flocking rules. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 2.6 Uniform node deployment and the density of nodes per 50*50m 2 region. The density is shown by the color-bar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.7 Deployment and the node density per 50*50m 2 region after applying the Thinning process on the deployment as shown by Fig. 2.6 with r b = 15 and N min = 6. The density is shown by the color-bar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 3.1 Effect of beamforming on the AP L and the CC when the nodes are using different antenna models. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.2 Asymmetric paths as a function of varying probability of rewiring. . . . . . . . . . . 46 3.3 Growth of AP L with increase in the network diameter. . . . . . . . . . . . . . . . . 46 3.4 Region Formation and Centroid identification using g = 5. . . . . . . . . . . . . . . . 53 3.5 The max degree nodes are not at the center of the region. The Closeness Centrality of these nodes is less. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.6 Relationship between beam properties and connectivity. . . . . . . . . . . . . . . . . 60 3.7 Nodes beamforming in different directions. . . . . . . . . . . . . . . . . . . . . . . . . 61 3.8 Beamforming priority. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 3.9 Beamforming nodes network depiction. . . . . . . . . . . . . . . . . . . . . . . . . . . 63 3.10 % number of nodes in GCC for nodes distributed uniformly and non-uniformly. . . . 68 xiii 3.11 Relationship between centroid nodes and the nodes having maximum Socio-Centric Betweenness. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.12 Results obtained for g ∈ [3, 10], when Sector model and non-uniform node distribution are used. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.13 Variation in the size of the GSCC and the GIN for different density of nodes and g ∈ [3, 10]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.14 Comparison of size of the GSCC and the GIN for directed network with that of omnidirectional network for g = 6. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.15 Results obtained for different g ∈ [3, 10], using U LA model and non-uniform node distribution. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.16 Normalized AP L and the CC for ρ = 2.5x10 -3 showing the effects of the region size for both the Sector and the U LA model. . . . . . . . . . . . . . . . . . . . . . . . . . 4.1 Probability of connection between the node i t and j ∈ N t i after ∆t time is given by the size of the dark line with red border. The circle in bold line represents C 1 , the circle in solid line represents C 2 . The dotted circle is the transmission range for j t+∆t . 4.2 Scenario when only one node acts as a source and has a single packet to transmit. . 4.3 Scenario when only one node acts as a source and has an update packet to transmit. 4.4 Scenario when multiple nodes act as source and each has single packet to transmit. . 4.5 Scenario when multiple nodes act as source and each has multiple packets to transmit. Sources can join as time ticks. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.6 fraction of nodes beamforming for different scenarios for Case A. . . . . . . . . . . . 4.7 fraction of nodes having packets when multiple nodes act as source and have multiple packets to transmit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.1 The evolution of the number of devices having information when the region is sub divided into many small communities and when the region has only one community. The results are obtained using the D4D dataset and SIR type epidemic model. . . . 5.2 D2D communication diagram. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.3 Visualization of datasets SPLoc and SPLocComp. . . . . . . . . . . . . . . . . . . . 5.4 SET3 user mobility on the graph. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.5 SET3 movement matrices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.6 Density of users from 16th December 2011 to 31st December 2011. . . . . . . . . . . 5.7 Mobility model showing the movements from one community to another one. . . . . xiv 5.8 State diagram with states S, I and R and their latent states E S , E I and E R respectively with transition rates between states. The square box represents the community i. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.9 Associating return rate to the mobility model. The dotted line shows the return rate from another community and is marked with ζ c ′ c and dotted line, rate of moving out of a community is given by σ c , while rate of going out to another community is marked with σ c ν cc ′ and solid lines. Each community has associated number of devices. For different communities these devices are marked in different color (white for i, red for j, blue for k). The color of the lines also represent which community the devices are associate to. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.10 Population density in each subprefecture on a log scale. . . . . . . . . . . . . . . . . 5.11 Evolution of fraction of devices in S, I and R states in Ivory Coast. . . . . . . . . . 5.12 Evolution of fraction of devices in active states in Ivory Coast. . . . . . . . . . . . . 5.13 Effects of beamforming. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.14 Evolution of difference in the number of devices in the active state. The difference is calculated between the case when sources are in two different communities and when the sources are in only one community. The number 2 and 1 in the legend suggest the how many communities generate the public warning message. . . . . . . . . . . . 5.15 Effect of constraining mobility on information dissemination. Both the results are obtained under similar setting and when x = 6% but one uses M P c while other uses M P v . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.16 Effect of mobility model on information dissemination. Both the results are obtained under similar setting and when x = 6%. . . . . . . . . . . . . . . . . . . . . . . . . . 5.17 Evolution of differences in number of devices in the three active states. The difference is calculated between the case when x = 6% and x = 0% for the mobility model with return rate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.1 Correlation between W F B and F BC for varying traffic load. . . . . . . . . . . . . . A.2 Selection of network using centralized and distributed choices of beamforming nodes using W F B. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3 Path length reduction by beamforming at nodes with high values of W F B. . . . . . A.4 Impact on unidirectional connectivity. . . . . . . . . . . . . . . . . . . . . . . . . . . A.5 Distribution of W F B values in the network. . . . . . . . . . . . . . . . . . . . . . . . A.6 Relation between β and p . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.7 Path length reduction by beamforming for distributed choice of nodes. . . . . . . . . A.8 Growth of average path length with the logarithm of the network size. . . . . . . . . xv A.9 Impact on unidirectional connectivity for distributed choice of nodes. . . . . . . . . . B.1 User density for subsets from A to D. . . . . . . . . . . . . . . . . . . . . . . . . . . B.2 User density for subsets from E to H. . . . . . . . . . . . . . . . . . . . . . . . . . . . B.3 User density for subsets from I to J. . . . . . . . . . . . . . . . . . . . . . . . . . . . B.4 Asymmetric property of conditional probability matrix for movement. . . . . . . . . B.5 Mobility Characteristics. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.1 Un sous réseau avec trois régions et g = 4. Ici le noeud x peut créer un faisceau vers y ou z, mais le nombre de hops vers y est plus que celui vers z, le noeud x crée un faisceau vers y. Les noeuds centraux sont noirs, les noeuds créant des faisceaux sont gris, les segments noirs représentent les connexions tandis que les segments rouges représentent les connections asymétriques. . . . . . . . . . . . . . . . . . . . . . . . . C.2 La probabilité de connexion entre les noeuds i et j ∈ N t i après un intervalle de temps ∆t est donnée par la taille de l'arc en gras. . . . . . . . . . . . . . . . . . . . . . . . C.3 L'évolution du nombre de machines ayant l'informations quand la région est divisée en beaucoup de petites communautés et quand la région n'a qu'une communauté. Les résultats ont été obtenus en utilisant des données du D4D et le modèle épidémiologique de type SIR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . C.4 Taux de retour pour le modèle de mobilité. La ligne pointillée montre le taux de retour depuis une autre communauté et est noté ζ cc ′ et la ligne pointillée correspondant aux mouvements dans la communauté est notée σ c , tandis que la ligne en trait plein correspondant au départ vers une autre communauté est notée σ c ν cc ′ . Chaque communauté correspond à un nombre de noeuds. Pour les différentes communautés, les noeuds ont des couleurs différentes (blanche pour i, rouge pour j, bleue pour k). La couleur des lignes représente aussi à quelle communauté elles sont associées. . . . xvi organized features to communication networks, insights from such naturally occurring phenomenon is used.

Figure 2 . 1 :

 21 Figure 2.1: Source: [2], (a) regular graph with p = 0, (b) small world graph with 0 < p < 1 where some of the edges from (a) were rewired, (c) random graph with p = 1 where complete rewiring of edges in graph (a) were performed.

Figure 2 . 2 :

 22 Figure 2.2: (a) regular graph with p = 0, (b) small world graph with 0 < p < 1 where edges were added to few nodes in (a), (c) random graph with p = 1 where edges were added to all the nodes in (a).

Figure 2 . 3 :

 23 Figure 2.3: The connectivity and temporal distance in the time varying graph.

  the direction of antenna boresight, B b . The maximum gain is also achieved at the antenna boresight (θ = B b ) and the radiation pattern is symmetric about the boresight B b . Using such setting, two basic antenna models, namely, Uniform Linear Array antenna model (U LA) and Uniform Circular Array antenna model (U CA), are defined. In the U LA model, the AEs are linearly arranged along the z axis. However, in the U CA model the AEs are circularly and symmetrically arranged on the yz plane. In both the models the distance between two AEs is ∆. Let c denote the velocity of light in vacuum, c = 3 × 10 8 m/s. Let f be the carrier frequency and λ = c/f . For simplicity, we define U LA model and will use it hereafter. For U LA model, radiation intensity is proportional to sin(M ψ) M * sin(ψ) 2

Definition 2 . 3 . 1 .

 231 Consider a graph, G(V, E) with set of nodes V and set of edges E such that |V | ∈ N and |E| ∈ Z + . Let there be ν components in the network such that 1 ≤ ν ≤ |V |. Let V i be B b = 0 o , 180 o . B b = ±30 o . B b = ±90 o .

Figure 2 . 4 :

 24 Figure 2.4: Gain pattern obtained for different B b and M = 8 when using U LA model.

Figure 2 . 5 :

 25 Figure 2.5: Depiction of three Flocking rules.

  Consider a spatial graph G(V, E) with set of nodes V and set of edges E such that |V | ∈ N and |E| ∈ Z + . Let the nodes in V be uniformly distributed in a region of area A where A ∈ R + and A > 0 (cf. Fig. 2.6). Thus the density of the nodes is ρ = |V |

Figure 2 . 6 :

 26 Figure 2.6: Uniform node deployment and the density of nodes per 50*50m 2 region. The density is shown by the color-bar.

Figure 2 . 7 :

 27 Figure 2.7: Deployment and the node density per 50*50m 2 region after applying the Thinning process on the deployment as shown by Fig. 2.6 with r b = 15 and N min = 6. The density is shown by the color-bar.

  1 β and Γ(a, b) as the incomplete gamma function defined as Γ(a, b) = ∞ b t a-1 e -t dt.

Definition 2 . 8 . 1 .

 281 Let A be the adjacency matrix of the graph G(V, E) with set of nodes V and set of edges E such that |V | ∈ N, |E| ∈ Z + and dimension of A = |V | × |V |. Let (A) ij denote the element in the i th row and j th column such that (A) ij ∈ {0, 1} and (A) ii = 0 for all i. Let D be the degree matrix such that size(D) = |V |x|V |, (D) ii = j∈V (A) ij and ∀j = i, (D) ij = 0. The Laplacian matrix L of a graph is defined as L = D -A.

Figure 3 . 1 :

 31 Figure 3.1: Effect of beamforming on the AP L and the CC when the nodes are using different antenna models.

Figure 3 . 2 :

 32 Figure 3.2: Asymmetric paths as a function of varying probability of rewiring.

Figure 3 . 3 :

 33 Figure 3.3: Growth of AP L with increase in the network diameter.

  and set of edges, E i such that E i ⊂ E where E = Nr i=1 E i . Let all nodes in V have (x, y) coordinates and a unique ID associated to them.

1

 1 j∈V hopcount ij . The node having maximum Closeness Centrality is the centroid of the graph and has a high structural importance. For the vertex sets defined above, nodes in the set P have lowest value of Closeness Centrality, i.e., arg max i∈V nodes in the set C have highest value of closeness centrality, i.e., arg min i∈V in P beamforms towards a node in C in order to minimize the distance to other nodes and reduce AP L.

  Distribution after applying Thinning process with r b = 1 and N min = 5. Identified regions in the deployment shown by the fig. 3.4(b).(d) The levels of the nodes created using the hopcount for the regions created in the fig.3.4(b). The peaks show the centroid nodes while the valley shows nodes with the max. distance from its associated centroid nodes. Association of the nodes to the centroid nodes. The centroid of the region is marked with a black square.

Figure 3 . 4 :

 34 Figure 3.4: Region Formation and Centroid identification using g = 5.

Figure 3 . 5 :

 35 Figure 3.5: The max degree nodes are not at the center of the region. The Closeness Centrality of these nodes is less.

  The peripheral nodes randomly choose the number of AEs, m ∈ [2, M ], to beamform. As described above for the sector model, B l = r × √ m and B w = 2π m . Note that to cover all the directions, minimum number of sectors that are needed are m. The dependency of B l and B w on m affects the connectivity of the network. Fig.3.6(a) shows the variation in B l and B w when m > 1.

2 - 1

 21 sectors. The complexity of such a test is O(M 2 ). This results into more energy consumption at the node. To reduce this energy consumption and the complexity to O(M ), the node selects randomly the number of AEs, m ∈ [2, M ], and only tests the corresponding set of m sectors.

  Fig. 3.8(a) and fig. 3.8(b)

  (a) The difference in the beam properties when a ℘ i uses different number of AEs. (b) Connectivity when 4 AEs are used. (c) Connectivity when 16 AEs are used.

Figure 3 . 6 :

 36 Figure 3.6: Relationship between beam properties and connectivity.

Figure 3 . 7 :

 37 Figure 3.7: Nodes beamforming in different directions.

Figure 3 . 8 :Figure 3 . 9 :

 3839 Figure 3.8: Beamforming priority.

Lemma 3 . 2 . 6 .

 326 For a node distribution and fully connected network with average node density ρ and total number of nodes |V |, then |C| is bounded by |V | ρg 2 r 2 π and |V | ρg 2 r 2 √ 3 .

3 2 .ρg 2 r 2 √ 3 . 3 . 2 . 7 .

 323327 Thus, for the area= |V | ρ , |C|= |V | Lemma Consider a network with j components (j > 1), average density of the nodes as ρ k and number of nodes as |V j k | for k ∈ j, |C| is bounded by j k=1 |V j k | ρ k g 2 r 2 π and |V |, where |V | =

Now using lemma 3

 3 .2.7 and lemma 3.2.5, the number of peripheral nodes for all regions thus varies between

Figure 3 .Figure 3 . 11 :

 3311 Figure 3.10: % number of nodes in GCC for nodes distributed uniformly and non-uniformly.

  Number of components in the network.

  Fraction of nodes designated as centroid nodes.

  )/APL(0) CC(p)/CC(0) (f) Normalized directional AP L and CC for ρ = 2.5 * 10 -3 showing the effects of the region size.

Figure 3 . 12 :

 312 Figure 3.12: Results obtained for g ∈ [3, 10], when Sector model and non-uniform node distribution are used.

Figure 3 . 13 :

 313 Figure 3.13: Variation in the size of the GSCC and the GIN for different density of nodes and g ∈ [3, 10].

(

  cf. Fig. 3.13). Comparing the size of the GSCC of directional network with the giant component of the omnidirectional network, (cf. Fig. 3.10), we find that the size of GSCC varies between [0.84, 0.94] for ρ = 2 * 10 -3 for different values of the region size while the size of giant component for the omnidirectional network is 0.41. Thus, an increase of almost 2.1 times. Fig. 3.14 shows an increase of almost 2.2 times when size of the GSCC and the GIN for g = 6 with the giant component of the omnidirectional network are compared.

Figure 3 . 14 :

 314 Figure 3.14: Comparison of size of the GSCC and the GIN for directed network with that of omnidirectional network for g = 6.

  Number of components in the network.

  Fraction of nodes designated as centroid nodes.

  )/APL(0) CC(p)/CC(0) (f) Normalized directional AP L and CC for ρ = 2.5 * 10 -3 showing the effects of the region size.

Figure 3 . 15 :Figure 3 . 16 :

 315316 Figure 3.15: Results obtained for different g ∈ [3, 10], using U LA model and non-uniform node distribution.

Fig. 3 .

 3 Fig.3.15(e),3.15(d)). From fig.3.16 it can be seen that, for higher density networks, the change in the AP L for the U LA model is more than that of the Sector model while the CC changes at a much lower rate.

Fig. 4 .

 4 1(b) and Fig. 4.1(d)).

  .1.1)

  (a) Case: a j + l j ≤ r.(b) Case: a j ≤ l j + r.(c) Case: a j > l j + r.(d) Case: a j + r ≥ l j .(e) Case: a j + r < l j .

Figure 4 . 1 :

 41 Figure 4.1: Probability of connection between the node i t and j ∈ N t i after ∆t time is given by the size of the dark line with red border. The circle in bold line represents C 1 , the circle in solid line represents C 2 . The dotted circle is the transmission range for j t+∆t .

Definition 4 . 1 . 1 .

 411 In a directed graph, in-degree of a node is the number of connections made to the node.

  (a) fraction of nodes having packet for different cases.

  (b) difference in fraction of nodes having packet.

Figure 4 . 2 :

 42 Figure 4.2: Scenario when only one node acts as a source and has a single packet to transmit.

B

  , C and D respectively. Thus we plot, I S * i -I y (cf. Fig. 4.2(b)). Fig. 4.2(b) shows the maximum improvement achieved over cases B, C and D is 0.05, 0.282 and 0.031, respectively. Note that as the scenario is single packet dissemination in the network, random direction beamforming performs equally well.

  (a) fraction of nodes having packet for different cases.

  (b) difference in fraction of nodes having packet.

Figure 4 . 3 :

 43 Figure 4.3: Scenario when only one node acts as a source and has an update packet to transmit.

Fig. 4 .

 4 3(b)). Fig. 4.3(b) shows the maximum improvement achieved over cases B, C and D is 0.065, 0.305 and 0.024, respectively.

  (a) fraction of nodes having packet for different cases.

  (b) difference in fraction of nodes having packet.

Figure 4 . 4 :

 44 Figure 4.4: Scenario when multiple nodes act as source and each has single packet to transmit.

Fig. 4 .

 4 4(b)) as a representation for Fig. 4.4(a). Fig. 4.4(b) shows the maximum improvement achieved over cases B, C and D is 0.0256, 0.665 and 0.141, respectively.

  (a) fraction of nodes having packet for different cases.

  (b) difference in fraction of nodes having packet.

Figure 4 . 5 :

 45 Figure 4.5: Scenario when multiple nodes act as source and each has multiple packets to transmit. Sources can join as time ticks.

  Fig 4.5(a)). When compared to the results obtained for multiple source single packet scenario, (cf. Fig. 4.4(a)), there is a shift of almost ≈ 20 time steps before at least one node can have packets from all the sources for Case A. This is because, sources are being added between t ∈ [0, 20] and last packet is generated at t = 25. We now show the difference in the fraction of nodes having packets, I S * i -I y , for different cases for this scenario (cf. Fig. 4.5(b)) as a representation for Fig. 4.5(a). Fig. 4.5(b)

Figure 4 . 6 :

 46 Figure 4.6: fraction of nodes beamforming for different scenarios for Case A.

Fig. 4 .

 4 7(d)). Similar results are obtained for varying M (cf. Fig.4.7(e)). When M is high the beam length is large and thus more distant nodes can be connected.Variations in S min and S max affect the number of nodes beamforming and to whom they beamform. Low value of S min reduces the number of nodes beamforming while a high value increases that number. This affects the information dissemination in the network, (cf. Fig 4.7(f)). However, low value of S max increases the number of nodes to which the nodes can beamform to, while a high value decreases that number. This affects the dissemination process (cf. Fig 4.7(g)).Next we show results obtained when different types of antennas are used. We use two different types of antennas, namely, U LA and a theoretical antenna model (Sector Model). U LA achieves better results than the Sector model because in U LA there is a secondary lobe with substantial beam length and width, (cf.Fig 4.7(h)). This increases the connectivity of the node as compared to when the Sector model is used. These results lead us to summarize the effect of each of the parameters, described above, on the information dissemination in Table4.3. for variable ρ.

  for variable α.

  for variable M .

  having packets S min =2e-05 S min =0.0002 S min =0.002 (f) for variable S min .

9 (

 9 g) for variable Smax.

  for different antenna models.

Figure 4 . 7 :

 47 Figure 4.7: fraction of nodes having packets when multiple nodes act as source and have multiple packets to transmit.

Figure 5 . 1 :

 51 Figure 5.1:The evolution of the number of devices having information when the region is sub divided into many small communities and when the region has only one community. The results are obtained using the D4D dataset and SIR type epidemic model.

  Ii number of devices in the community i|i ∈ C that are latent, contain the information and will transmit it when becoming active E Si number of devices in the community i|i ∈ C that are latent and do not contain the information E Ri number of devices in the community i|i ∈ C that are latent, contain the information and will not transmit it E Iij number of devices in the community i|i ∈ C that are latent, contain the information, will transmit it when becoming active and have home community j|j ∈ C E Sij number of devices in the community i|i ∈ C that are latent, do not contain the information and have home community j|j ∈ C E Rij number of devices in the community i|i ∈ C that are latent, contain the information, will not transmit it and have home community j|j ∈ C G c complete graph obtained by joining all subprefectures G v graph obtained after delaunay triangulation of subprefectures position g q,θ,B b gain achieved using antenna array H home community I i number of devices with information those who will transmit the information in the community i|i ∈ C I ij number of devices with information those who will transmit the information in community i|i ∈ C that have home community j|j ∈ C M maximum antenna elements available M P v conditional probability matrix for movement on G v M P c conditional probability matrix for movement on G c M R v movement rate matrix on G v M R c movement rate matrix on G c M RR v return rate matrix on G v M RR c return rate matrix on G c m number of antenna elements used by the device to beamform |m ∈ [2, M ] N ij number of devices that have home community as i but are in community j|i, j ∈ C N * i steady state population of community i|i ∈ C N i initial population of community i|i ∈ C N total population considered Continued on Next Page. . .

Figure 5 . 2 :

 52 Figure 5.2: D2D communication diagram.

The

  D4D dataset provided to us as part of a research project has the following structure. It contains the central location of the subprefecture area and the position of antennas in longitude and latitude format along with four sub-datasets (SET1, SET2, SET3 and SET4) out of which we are interested only in SET3 which contains mobility information. SET3 contains information of 500,000 users over 5 months from 5th December 2011 until 28th April 2012. Each tuple in SET3 contains subprefectureID from where the call was made, time when the call was made and userID of the users who made the calls. Mobility of a user from this dataset can be estimated.Consider a user u. A query "SELECT subprefectureID from SET3 where userID=u" on the SET3 results into a list of subprefectureIDs that the user made calls from. The list may have different subprefectureIDs. Whenever a change in the subprefectureID is observed in the list, it is said that the user has moved to the new subprefecture and has called from there. Due to this reason SET3 is also called mobility dataset by the D4D Organizers. Further, as the actual coordinates of a user are missing and only subprefecture coordinates are available, the mobility of the users can only be determined approximately.

  SPLoc contains the information about the central position in a subprefecture region. A tuple in SPLoc contains, subprefectureID, x coordinate of the central position in the subprefecture region and the y coordinate of the central position in the subprefecture region. These x, y coordinates are in longitude and latitude format. Consider x, y coordinates in SPLoc as the locations of the set of nodes V in a spatial graph where V is the set of subprefectureIDs in SPLoc. Using this information, we visualize a Voronoi tessellation for the subprefectures in the region of Ivory Coast (cf. Fig. 5.3(a)). A cell in Voronoi tessellation could represent a cell (coverage area of an eN B) in a D2D communication network setup (cf. Fig. 5.2). Actual subprefecture boundaries also provide hypothetical coverage area and can be related to the coverage area of an eN B. Using this Voronoi tessellation we generate the dual of Voronoi tessellation, Delaunay triangulation. The Delaunay triangulation, in this context, represents a graphical structure that connects all neighboring subprefectures in the same country. We call the graphical structure G v , (cf. Fig. 5.3(b)). This dataset is complemented with another dataset (SPLocComp) which contains the actual subprefecture boundaries. The SPLocComp dataset also contains information about which subprefecture lies in which department. This leads us to visualize the department-subprefecture relation based on the departments to which subprefectures are assigned, (cf. Fig. 5.3(c)).

( a )

 a Voronoi tessellation for the subprefectures in Ivory Coast with subprefecture locations. (b) Gv.(c) Association of subprefecture to departments in Ivory Coast.

Figure 5 . 3 :

 53 Figure 5.3: Visualization of datasets SPLoc and SPLocComp.

  (a) Estimate of subprefectures reached by user 297412 using Gv.(b) Subprefectures reached by user 297412 using Gc.

Figure 5 . 4 :

 54 Figure 5.4: SET3 user mobility on the graph.

Figure 5 . 5 :Figure 5 . 6 :

 5556 Figure 5.5: SET3 movement matrices.

Figure 5 . 7 :

 57 Figure 5.7: Mobility model showing the movements from one community to another one.

Figure 5 . 8 :

 58 Figure 5.8: State diagram with states S, I and R and their latent states E S , E I and E R respectively with transition rates between states. The square box represents the community i.

  Evolution of S total , I total and R total in Ivory Coast using simple SIR model. Evolution of fraction of devices in S, I and R states in community one and three in Ivory Coast using simple SIR model.

Figure 5 . 11 :

 511 Figure 5.11: Evolution of fraction of devices in S, I and R states in Ivory Coast.

Fig. 5 .

 5 [START_REF] Sayama | Complex System Organization Map[END_REF].The results show, the fraction of devices in state I for the case where sources are in two different communities, differ between[-13365, 236460] in the non normalized case ([-0.00085, 0.015073]% in the normalized case) from the case when the sources are only in a single community. The results Evolution of fraction of devices in S, I and R states for case A and case B.

  Evolution of fraction of devices in S, I and R states for case A and case B when normalized by the fraction of active devices. S total,active I total -I total,active R total -R total,active (c) Difference in number of devices in active states normalized over active population for case A and case B.

Figure 5 . 12 :

 512 Figure 5.12: Evolution of fraction of devices in active states in Ivory Coast.

  x =6% -S total,x =0% I total,x =6% -I total,x =0% R total,x =6% -R total,x =0% (b) Evolution of difference in the number of devices in the active states in Ivory Coast for case B ′ and case B. The results are normalized over active population.

  x =10% -I total,x =0% I total,x =6% -I total,x =0% I total,x =2% -I total,x =0% (c) I total,x=y% -I total,x=0% when y = 2%, y = 6% and y = 10%.

Figure 5 . 13 :Figure 5 . 14 :

 513514 Figure 5.13: Effects of beamforming.

Figure 5 . 15 :

 515 Figure 5.15: Effect of constraining mobility on information dissemination. Both the results are obtained under similar setting and when x = 6% but one uses M P c while other uses M P v .

  total -S mobility2,total I mobility1,total -I mobility2,total R mobility1,total -R mobility2,total

Figure 5 . 16 :

 516 Figure 5.16: Effect of mobility model on information dissemination. Both the results are obtained under similar setting and when x = 6%.

Figure A. 1 :

 1 Figure A.1: Correlation between W F B and F BC for varying traffic load.

  rank in the network, rank correlation of the two measures is obtained. The nodes are ranked in the network separately according to their W F B and F BC values and Spearman's correlation coefficient is found between two as ρ Centralized choice of nodes ranked by W F B values Distributed choice of beamforming nodes

Figure A. 2 :

 2 Figure A.2: Selection of network using centralized and distributed choices of beamforming nodes using W F B.

r 2 ⌉

 2 is achieved by reduction in beam width. The narrow beam width reduces the probability of a node maintaining connectivity to its omnidirectional neighborhood. The second probability p nl indicates the probability that at least one node benefits from the increased beam length. If there are no nodes present in the last region, greater connectivity can be achieved by increasing the beam width while the improvements from the beam length stay the same. The nodes in the middle regions of the beam are not used in the expression since they do not represent the maximum benefits achievable by increased beam length nor are they the most affected in terms of connectivity as a result of reduced beam width. The values for p nf and p nl are obtained based on the node density in the network. Given that the number of nodes in the omnidirectional neighborhood of a node is n, the corresponding values are obtained asp nf = 1 -(1 -A f πr 2 ) n and p nl = 1 -(1 -A lπr 2 ) n where A f and A l are the area of the first and last regions respectively. Recall that the area under the beam is equal to that of the omnidirectional area when the same transmit power is used. The value of m, number of antenna elements, used is computed as m = ⌈ r(B * w ) where r(B * w ) is the transmission range after beamforming.Further, nodes orientate their beams in a direction in which they record the maximum hop count based on earlier traffic flows, so as to minimize the network diameter. The simulation results shown here only consider the sector model. The results are compared for nodes distributed at two different node densities. A high node density of d = 4.6 nodes per unit area results from distributing 300 nodes over an 8x8 region, and a lower density of d = 3 is obtained by increasing the region size to 10x10 for the same number of nodes. Subsequently, the density is kept constant at either of these two values and only the the size of the region is varied.

  Fig. A.2(b) shows the set of nodes chosen as beamforming nodes for the network setup shown in A.2(a). It can be seen that the majority of the nodes chosen (circled in red) are located towards the center of the network.

Fig. A. 3 Figure A. 4 :

 34 Fig. A.3 illustrates the impact on path length reduction. A reduction of more than 40% and 30% are shown to be achievable for d = 4.6 and d = 3 respectively in Fig. A.3(a). Here, it is notable that the improvements in both cases are higher than the corresponding value of p for randomized beamforming. As the network size increases, the beam length to diameter ratio reduces to r(B * w ) D ≈ 0.2 for d = 3 and r(B * w ) D≈ 0.25 for d = 4.6. Using the results in[START_REF] Helmy | Small Worlds in Wireless Networks[END_REF] as a benchmark, we find that the path length reduction is greater for corresponding values of r D . The results in Fig.

Fig. A. 4

 4 Fig. A.4 shows the impact of directional beamforming using W F B on the fraction of node pairs that are unidirectionally connected. The effect on unidirectional connectivity is negligible for d = 4.6.

  Figure A.5: Distribution of W F B values in the network.

Figure A. 6 :

 6 Figure A.6: Relation between β and p

  Figure A.7: Path length reduction by beamforming for distributed choice of nodes.

Figure A. 8 :

 8 Figure A.8: Growth of average path length with the logarithm of the network size.

Figure A. 9 :

 9 Figure A.9: Impact on unidirectional connectivity for distributed choice of nodes.

Fig. A. 7

 7 Fig. A.7 illustrates the path length reduction for node densities d = 3 and d = 4.6 nodes per unitarea for both the sector and U LA models. When using the sector model, the path length reduction achieved is higher than in the case of centralized choice of nodes. This additional benefit is again due to the fact that fewer fraction of nodes that are omnidirectional neighbors beamform as a result of the proposed algorithm. Directional beams that are located close to each other tend to reduce the improvement in path length as only one of the two may get chosen most of the time, thereby rendering the other redundant. The performance for the U LA model is even more promising as greater than 40% reduction is achieved in both cases, with the improvement being greater than 50% for greater size of the network region with d = 4.6. Fig. A.8 shows the growth in path length for d = 4.6 with respect to the logarithmic of the network size. As the choice of beam width is the same as earlier, we obtain a similar values of r(B * w ) D ≈ 0.2 for d = 3 and r(B * w ) D ≈ 0.25 for d = 4.6 when the network size increases. The reduction in path length, is, therefore, much higher than corresponding values of r D and p shown in [48]. The impact on connectivity is illustrated in Fig. A.9. As in the case of centralized choice of nodes, the fraction of node pairs unidirectionally connected is negligible for higher node density, d = 4.6. For lower node density d = 3 as well, the impact on connectivity is lower than in the earlier case.

  Fig. B.1 to B.3) and extract mobility information in terms of M P c and M P v as shown in Section 5.2.2. Both M P c and M P v are asymmetric matrices (cf. Fig. B.4(a) to B.4(b)

  User density for subset J.

Figure B. 3 :

 3 Figure B.3: User density for subsets from I to J.

  |M Pc(ij) -M Pc(ji)|.

  |M Pv(ij) -M Pv(ji)|.

Figure B. 4 :

 4 Figure B.4: Asymmetric property of conditional probability matrix for movement.

Figure B. 5 :

 5 Figure B.5: Mobility Characteristics.

  Dans les réseaux sans-fils, même si on utilise des informations locales dans un environnement autonome, le plus important est toujours de transmettre efficacement les informations d'un noeud à l'autre, en dépit des contraintes citées précédemment. Dans un environnement réel, dans les réseaux sans-fil, la transmission des informations est affectée par beaucoup de facteurs comme le déploiement non uniforme, la topologie dynamique, le manque d'infrastructure centralisée et les ressources limitées. De plus, dans différents types de réseaux mobiles, plusieurs propriétés associées affectent la diffusion des informations. Par exemple dans les réseaux mobiles sans fil, et en particulier dans les réseaux PSN (Pocket Switched Networks) et les réseaux de communication D2D (Device to Device) les caractéristiques du comportement humain et les schémas de la mobilité humaine affectent la diffusion des informations. Considérons un message d'alerte publique qui a à être diffusé dans la population. Dans les réseaux statiques (un réseau qui ne change pas pendant une durée fixée), le déploiement non uniforme de noeuds conduit à un réseau comportant plusieurs sous-réseaux déconnectés. La diffusion des informations entre deux sous réseaux ne sera pas possible avant qu'une connexion soit créée entre chacun des couples de sous-réseaux. Cela limite la diffusion des informations à une fraction de la population. Dans le cas d'un message d'alerte publique, il n'est pas suffisant qu'une fraction de la population reçoive le message. La totalité de la population doit pouvoir le recevoir. Considérons un réseau statique, où les noeuds ne bougent pas et n'ont aucune des caractéristiques des noeuds mobiles. Maintenant supposons qu'une perturbation est apparue dans le réseau et a causé quelques changements dans la topologie du réseau. Par exemple les facteurs qui peuvent causer une telle perturbation seraient les suivants: un noeud pont dans l'un des sous-réseaux peut avoir été enlevé du sous-réseau, à cause des limitations concernant l'énergie, ce qui amène le sous-réseau à être coupé en plusieurs sous-réseaux plus petits. Autres exemples les catastrophes naturelles comme les glissements de terrains, tremblements de terre. Dans ces cas un réseau fortement connecté peut être cassé en plusieurs sous-réseaux et on peut arriver à un réseau déconnecté. L'auteur appelle néanmoins le nouveau réseau un réseau statique car à moins d'un événement imprévu comme ceux qui ont été cités, la structure du réseau ne va pas changer pendant une période assez grande. Dans les catastrophes une diffusion rapide des messages d'alerte joue un rôle important. Plus les secours arrivent vite, mieux c'est. Cependant à cause des changements dans la topologie du réseau, il se peut que le réseau soit coupé en plusieurs sous-réseaux déconnectés, et la diffusion des informations est fortement influencée. Quand les noeuds d'un réseau sans-fils sont mobiles (Mobile ad hoc Network, Pocket Switched Networks, Delay Tolerant Networks, Device to Device communication network), la topologie du réseau change souvent et ces changements causent des changements dans le processus de diffusion.Les modèles de mobilité, principalement reliés aux modèles de mobilité pour les usagers qui transportent les appareils ou qui les supervisent peuvent amener le réseau à être déconnecté et entraver la diffusion des informations. Cependant certaines études révèlent que la diffusion des informations est améliorée par la mobilité. Dans les modèles de métapopulation, les modèles de communautés basés sur les interactions, il a été prouvé que la mobilité améliore le processus de diffusion des informations.Cependant dans un scenario où les messages d'alertes doivent être diffusés rapidement à la totalité du réseau, une tâche difficile est de concevoir un algorithme efficace et juste qui permette d'atteindre cet objectif le plus tôt possible Qu'il soit mobile ou statique, le réseau est très dynamique, compte tenu des besoins croissants et des changements de technologie. Dans les scenarii réels, il y a une population dynamique qui peut causer à n'importe quel moment des changements importants dans le réseau ; ces changements ont naturellement une influence forte sur la diffusion des informations.

  Cependant dans les réseaux sans-fils mobiles, l'algorithme cité précédemment créerait un "overhead" important, à cause des changement fréquents de la topologie du réseau. Fasciné par les propriétés des PSN (pocket switch networks), l'auteur dans la section C.3 propose d'utiliser le concept de stabilité et le "beamforming" pour accélérer la diffusion des informations. Dans les PSns les propriétés du réseau dépendent beaucoup des modèles de mobilité, à chaque instant le réseau évolue et des communications D2D existent. Récemment, il a été montré que la répartition des sauts de la mobilité de l'homme pouvait être estimée en utilisant une loi puissance tronquée[START_REF] González | Understanding Individual Human Mobility Patterns[END_REF] ce qui pourrait conduire à une répartition non uniforme de la population humaine dans la région. Ceci pourrait amener le réseau à être déconnecté et entraver la diffusion des informations. Par ailleurs la mobilité peut aussi améliorer la diffusion en créant de nouvelles connexions dans le réseau[START_REF] Kivelä | Multiscale Analysis of Spreading in a Large Communication Network[END_REF]. En utilisant les propriétés de la mobilité, l'auteur propose dans la section C.3 de calculer la stabilité d'un noeud en utilisant des informations locales et le modèle de mobilité et d'utiliser la valeur obtenue pour améliorer la diffusion des informations. Dans la section C.3 l'auteur définit la stabilité comme le nombre de connexions qui sont inchangées. La valeur de la stabilité est alors utilisée pour identifier les noeuds qui créent un faisceau et les noeuds vers lesquels ils le font.

  [START_REF] Csáji | Exploring the Mobility of Mobile Phone Users[END_REF] montra que la répartition de la mobilité humaine peut être modélisée par une loi lognormale. Les différences entre les modèles de mobilité ont conduit l'auteur à acquérir des données D4D et à participer au challenge[START_REF] Blondel | Data for Development: The D4D Challenge on Mobile Phone Data[END_REF] organisé par Orange Labs et le MIT. Les données concernaient les traces des appels et les déplacements des usagers du réseau Orange en Côte d'Ivoire. L'analyse des données a montré que la distribution des déplacements humains de la Côte d'Ivoire est une loi Gamma. Dans de grandes populations distribuées géographiquement, appelées souvent métapopulation, où les interactions sont basées sur les mouvements et sont des interactions de proximité, la diffusion des informations dans les métapopulations utilisant des modèles de mobilité humaine, ont été bien étudiées[START_REF] Arino | Disease Spread in Metapopulation[END_REF][START_REF] Watts | Multiscale, Resurgent Epidemics in a Hierarchical Metapopulation Model[END_REF] en utilisant des modèles épidémiologiques. Cependant les cas de réseaux sans-fils mobiles réels D2D où la densité des noeuds du réseau change constamment ont été négligés jusqu'à présent. Les deux sections C.2 et C.3 de cette thèse ont utilisé des algorithmes de diffusion des informations traditionnels et considéré une densité des noeuds fixe au cours du temps. Dans la section C.4 l'auteur montre l'influence d'une densité dynamique sur la diffusion des informations et celle du "beamforming" et la mobilité peuvent être utilisés pour améliorer la diffusion dans un scenario de communication D2D. Dans la section C.4 l'auteur propose une mise à jour du modèle épidémiologique classique SIR, ajoutant 3 états, E S , E I et E R , afin d'avoir une densité dynamique des noeuds. Chaque état du modèle SIR est ainsi associé à un état supplémentaire. L'auteur appelle ces états supplémentaires des états latents. Les noeuds en état latent ne participent pas à la diffusion des informations. Cependant si un noeud devient actif, il participe à nouveau à la diffusion. Les transitions entre les trois états actifs (S, I, R) et les états latents et vice versa, se produisent avec un taux donné. C.1.3 Organisation Le manuscrit est ensuite organisé de la façon suivante: il donne une vue d'ensemble des algorithmes développés par l'auteur dans la section C.2, la section C.3 et la section C.4 respectivement. Le manuscrit conclut dans la section C.5 et présente des directions futures dans la section C.6. C.2 Obtention des Propriétés des "Small World" dans le Réseau Sansfils grâce à des Techniques Bio-inspirées Dans cette section, l'auteur examine comment on peut obtenir une augmentation de la connectivité, une réduction de la longueur moyenne des chemins AP L et une quasi-conservation du coefficient de clusterisation CC dans un réseau sans fil non uniformément distribué, en utilisant des informations locales uniquement et du "beamforming". L'auteur crée des grands faisceaux entre 2 noeuds qui ont une faible et une forte importance. La nécessité de calculs décentralisés et d'auto-organisation amènent l'auteur à s'inspirer des phénomènes naturels et à utiliser: l'inhibition latérale

L

  'inhibition latérale est une technique où les noeuds empêchent les noeuds voisins de réaliser une tâche. Dans l'algorithme, l'inhibition latérale amène les noeuds non inhibés à inhiber les noeuds qui sont à moins de g hops d'eux. Les noeuds inhibés forment une région. L'utilisation de l'inhibition latérale ne réduit pas seulement la complexité du message, elle permet d'utiliser avec succès la migration par groupe, en effet elle permet d'identifier les noeuds qui vont créer des faisceaux et de définir les propriétés des faisceaux. Selon les règles de la migration: alignement, séparation et cohésion, il est important d'identifier les noeuds isolés, d'aligner les noeuds, de les séparer et de les déplacer en direction du centre de leur voisinage. De façon analogue, après avoir créé des régions en utilisant l'inhibition latérale dans un réseau sans-fil ad hoc non uniformément distribué, l'auteur utilise les règles de la migration en groupe pour identifier les noeuds qui créent un faisceau et diriger ce faisceau vers le centre de la région identifiée. Le noeud central est un noeud qui a une grande importance pour la structure du réseau. Les noeuds qui créent des faisceaux sont les noeuds les plus éloignés du noeud central de la région. Ce processus est analogue à l'indentification des groupes ou à la règle d'alignement. Créer un faisceau vers le noeud central d'une région contribue à diminuer la longueur moyenne des chemins car le noeud central est le noeud le plus connecté, a la plus grande mesure de centralité de voisinage et est le plus éloigné du noeud qui crée un faisceau.

Figure C. 1 :

 1 Figure C.1: Un sous réseau avec trois régions et g = 4. Ici le noeud x peut créer un faisceau vers y ou z, mais le nombre de hops vers y est plus que celui vers z, le noeud x crée un faisceau vers y. Les noeuds centraux sont noirs, les noeuds créant des faisceaux sont gris, les segments noirs représentent les connexions tandis que les segments rouges représentent les connections asymétriques.

  Figure C.2: La probabilité de connexion entre les noeuds i et j ∈ N t i après un intervalle de temps ∆t est donnée par la taille de l'arc en gras.

Figure

  Figure C.3: L'évolution du nombre de machines ayant l'informations quand la région est divisée en beaucoup de petites communautés et quand la région n'a qu'une communauté. Les résultats ont été obtenus en utilisant des données du D4D et le modèle épidémiologique de type SIR.

  The temporal degree of a node i, T D i , is the average degree of the node over time period [t, t ′ ) and is defined as

Kim et al. in [63] also defined Temporal Degree (T D) of a node i over a time period based on the degree of the nodes at each instant of time. Consider N t i as the neighborhood of the node i at time t such that 0 ≤ |N t i | ≤ |V | and N t i ⊂ V . The degree of node i at time t is given by |N t i |.

Table 3 .

 3

	Parameter\ Proposed	Abhik	Guidoni	Helmy	Sharma	Verma
	Reference	Algorithm	et al. [1]	et al. [124] et al. [48] et al. [123] et al. [125]
	Shortcut	Rewiring	Rewiring	Addition	Addition	Addition	Addition
	Creation
	Node	Non Uniform Uniform	Uniform	Uniform	Uniform	Uniform
	distribution
	External	No	No	High range	-	Wired	Two radios
	infrastructure			Sensor			for each node
	Global	No	No	Yes	Yes	Yes	Yes
	knowledge
	Density of	Low	High	High	High	-	Low
	nodes
	Shortcut	Directed	Directed	Undirected	Undirected Undirected	Directed
	Edge
	Shortcut	Towards	Longest	Random,	Random	Random	Random
	direction	centroid of	Traffic	towards sink
		other region	Flow path
	Shortcut	Function of	Function of	Constant	Limited	Constant	Constant
	length	antenna	node density
		elements
	Shortcut	Depends on	Depends on	Constant	-	-	Constant
	width	Shortcut	Shortcut
		Length	Length
	Probability of Shortcut	(0, 1] based on model	Function of β	∈ (0, 1]	∈ (0, 1]	function of network	∈ (0, 1]
	creation	parameters				size
	Performance	AP L,	AP L,	AP L,	AP L,	AP L,	AP L,
	metric	CC,	Connectivity CC	CC	Energy	CC,
		Connectivity					Degree

1

Sector model approximates realistic antenna models 1: Comparison between various researches related to achieving Small World characteristics in wireless networks. More details on Abhik et al. algorithm

[START_REF] Banerjee | A Self-Organization Framework for Wireless Ad Hoc Networks as Small Worlds[END_REF]

are provided in appendix A .

  where N hi is the set of neighborhood nodes of h i such that |N hi | ≥ 0). Let H be the set of all head nodes. Initially, all the nodes consider themselves as heads, i.e. H = V , and store their own information, i.e., h i = i, hopcount = 0 and deg(h i ) = |N

i |. Each node, i ∈ V , then broadcasts this information to its neighbors, N i . Similarly, i receives information from each of its neighbors and subsequently updates the information stored in it. A node updates its stored values, if the stored degree, deg(h i ), is less than that of the received value and hopcount + 1 is less than g, where g is the hop limited desired region size such that g ∈ Z + . If the stored and the received deg(h i ) are same, the node decides to update the stored information based on lower hopcount value. If the stored

  Separation rule of Flocking provides insight towards this problem.

	Algorithm 2 Region formation

1: Let U ← uninhibited; 2: Let I ← inhibited; 3: Let ID ← identity of node; 4: \\ Region formation; 5: for all i ∈ V do 6:

  3.2.3.The number of regions is equal to number of centroid nodes and each region has exactly one centroid node.Proof. The algorithm computes the centroid of the region based on average of coordinates, Degree and Egocentric Betweenness of the node for each region. According to the algorithm, the nodes are termed as centroid if the node falls within ε range of the centroid coordinate estimation algorithm

	3:	if hopcount jci > hopcount Nj,ici then
	4: 5: 6:	P i ← P i + {j} P ← P + {j} end if
	7: end for
	8: \\ Separation; 9: for all ℘ i ∈ P i ∈ P do 10: set m
	11: 12: 13:	for all m Sectors |̺ ℘i (B b ) / ∈ Sectors do RC * ℘i ← RC * ℘i + {reachable centroid nodes} end for
	14: end for
	15: \\ Cohesion;
	24: 25:	h ← h + hopcount ℘ic end for
	26:	else
	27: P 28: end if
	29:	end if
	30: 31:	beamtonode ← max{h}

and have maximum sum of Degree and Egocentric Betweenness. If still there are multiple nodes Algorithm 4 Beamforming using Flocking Analogy

1: \\ Alignment; 2: for all j ∈ V i ∈ V do 16: for all ℘ i ∈ P i ∈ P do 17: if RC * ℘i -RC ℘i = ∅ then 18:

for all c ∈ RC * ℘i -RC ℘i do 19: h ← h + hopcount ℘ic 20: end for 21: else 22:

if RC ℘i = ∅ then

23:

for all c ∈ RC ℘i do i ← P i -{℘ i }

Table 4 .

 4 1 details the notations used in this Chapter hereafter. The rest of this Chapter is circle of radius a j centered at j t C 2 circle of radius r centered at j t+∆t D 1 disk of radius a j centered at j t D 2 disk of radius r centered at j t+∆t E t set of edges at time t G initial network of set of nodes V and set of edges E G t instance of G at t with set of nodes V and set of edges E t i a device in V i t node i at time t l j distance between initial position of neighborhood node and the final position of i M maximum number of antenna elements available with i ∈ V m number of antenna elements used by i ∈ V to beamform |m ∈ [2, M ]

	Notation Meaning
	A	simulation area
	a j B b	i jump of j such that j ∈ N t boresight direction
	b j	jump of i
	C 1
	N t i	set of neighborhood nodes of i at time t
	r	transmission radius
	S * i	stability of the node i
	S max	maximum stability threshold
	S min	minimum stability threshold
	t	time
	x min	minimum jump length
	θ j	connectivity angle
	∆t	change in time
	α	power law exponent constant
	β	exponential cutoff constant
	ρ	density of devices in the region

Table 4 .

 4

1: Notations and their meaning. structured such that it first provides the algorithm outline in Section 4.1 and the results obtained in Section 4.2. We conclude the Chapter by presenting conclusion of the study in Section 4.3.

  Let the set of neighbors at a given time t be denoted by N t i . Note that 0 ≤ |N t i | ≤ |V | and N t i ⊂ V . The connectivity of the devices in V constitutes a network (graph) G t with |V | devices and |E t | edges, where E t is the set of edges in the graph at time t such that |E t | ∈ Z + .

Table 4 .

 4 3: Factors affecting the dissemination of packet. The table shows the effect on the time taken to disseminate the information in the network completely when the parameter value increases.

	Number of sources	↑	↑
	Number of packets	↑	↑
	Other Parameters
	Stability measure type		different
	Type of antenna array		different

Next we show the results obtained when r and M vary. Results clearly state that when r is high, more nodes are connected and the dissemination of packets is faster, (cf.

Table 5 .

 5 ) ij the number of times a user u traversed through edge between node i and j. Si transition rate from state E Si to S i α Ii transition rate from state E Ii to I i α Ri transition rate from state E Ri to R i

	1 -Continued

ij number of devices with information those who will not transmit the information in community i|i ∈ C that have home community j|j ∈ C r transmission radius S i number of devices without information in community i|i ∈ C S ij number of devices without information in community i|i ∈ C that have home community j|j ∈ C SP ij shortest path between community i and j|i, j ∈ C i expected number of connections for a device in community i|i ∈ C when beamforming is applied Table 5.1: Notations and their meaning.

  2. Finally, theAppendix concludes in Section A.3.

	Notation Meaning
	a f (v)	additional flows for node v
	B w B * w	beam width chosen beam width
	D	diameter of the network
	d i	absolute difference in ranks of the node i
	f	fraction of nodes generating packets
	g(v)	number of packets forwarded by node v
	L(p)	Average path length of the network corresponding to p
	m	number of antenna elements in a directional antenna
	N (v) o(v)	Set of neighbors of node v number of packets overheard by node v
	p	fraction of edges rewired or nodes beamforming
	p nf	probability that at least one node is located in the first sectoral region
	p lf	probability that at least one node is located in the last sectoral region
	r	omnidirectional transmission range
	V	the set of all nodes in the network
	w(v)	betweenness of node v
	β	similarity factor
	ρ	Spearman's correlation coefficient
		Table A.1: Notations and their meaning.
	A.1 A Distributed Definition of Centrality for Wireless Ad hoc Net-
	works

  1, which was used for the earlier set of simulations using centralized choice of nodes. Using simulations, we identify this value as β = 2 which results in values of p between 0.11 -0.13. The relation between β and p is shown in Fig. A.6. The results are obtained using the sector model as well as the realistic

		0.1											0.1
	Fraction of Asymmetric Paths	0.02 0.04 0.06 0.08						WFB, Sector WFB, ULA Rnd, Sector Rnd, ULA		Fraction of Asymmetric Paths	0.02 0.04 0.06 0.08						WFB, Sector WFB, ULA Rnd, Sector Rnd, ULA
		0	8	9	10	11	12	13	14	15	16	17	0	8	9	10	11	12	13	14	15	16	17
							D											D
						(a) d = 4.6									(b) d = 3

  Quand le réseau est mobile, la diffusion des informations est aussi influencée par les caractéristiques des régions comme la densité et la distribution de la population dans la région. Dans un réseau sans-fils où les noeuds ont une énergie limitée et une taille mémoire limitée, l'utilisation d'informations locales diminue les dépenses d'énergie et de mémoire.Les interactions des noeuds avec leur environnement jouent aussi un rôle très important pour définir les propriétés des noeuds pour obtenir des transferts de données efficaces et une bonne diffusion des informations. Les propriétés des "small world"[START_REF] Watts | Collective Dynamics of Small World Networks[END_REF] sont connues: on peut réduire la longueur moyenne des chemins en recâblant les liens, tout en maintenant la structure du réseau. Il y a une relation directe entre la vitesse de diffusion des informations dans le réseau et la longueur moyenne des chemins car le diamètre du réseau est réduit. Dans les réseaux sans-fil, cependant le recâblage peut être réalisé par la technologie M IM O en adaptant le rayon de transmission au rayon de réception. veut limiter le nombre des noeuds qui créent des faisceaux. Le choix des noeuds qui créent un faisceau et les caractéristiques du faisceau sont les points essentiels de la section C.2. Ce choix, ainsi que le choix des noeuds vers lesquels le noeud crée un faisceau est réalisé en utilisant l'analogie avec les migrations en groupes et l'inhibition latérale. Comme dans la nature où on observe trois règles pour les migrations en groupe: alignement, cohésion et séparation, l'auteur crée des règles: il relie l'alignement à la décision des noeuds de créer ou non un faisceau, la cohésion au choix de la direction du faisceau vers le noeud le plus central, et la séparation au fait que deux noeuds ne doivent pas créer des faisceaux dans la même direction. Pour déterminer le noeud le plus central, l'auteur utilise l'inhibition latérale. C'est aussi cette inhibition qui permet de créer des régions logiques telles que seuls les noeuds dans la périphérie de la région peuvent créer un faisceau en direction des noeuds

	locales qui peuvent minimiser les "overheads" et garantir les performances pour le fonctionnement cela pourrait générer des dissymétries et le réseau pourrait perdre sa structure. C'est pourquoi
	Les difficultés résoudre ont amené l'auteur à étudier comment le processus de diffusion des informations peut être à amélioré dans le réseau où les noeuds n'ont pas une connaissance globale du réseau et sont réduits à une connaissance à un saut. Si le réseau est statique et déconnecté, la question posée est: comment les propriétés d'un noeud peuvent-elles être utilisées pour diffuser les informations d'un sous-réseau à du réseau sans-fils. noeuds statiques autonomes dans un réseau comprenant plusieurs sous-réseaux. L'autonomie amène l'auteur
	un autre? Si le réseau est mobile la question est: comment le processus de diffusion des informations l'auteur à proposer une approche centralisée où les noeuds communiquent directement comme dans
	peut-il être amélioré? une communication D2D. L'auteur utilise la création de faisceau, "beamforming", afin de permettre
	des communications entre les sous-réseaux déconnectés. Comme le suggèrent les propriétés des "small
	C.1.2 Motivation et Contributions world" un petit nombre de liens recâblés peuvent changer de façon radicale la longueur moyenne
	des chemins tout en conservant intacte la structure du réseau. Cependant le "beamforming" peut
	Intéressons-nous à un réseau sans-fils, dans un environnement qui change en permanence, il est générer des dissymétries et réduire la taille des voisinages. Si tous les noeuds créaient des faisceaux,
	important pour les chercheurs de concevoir et d'analyser des algorithmes utilisant des informations

Ceci peut être réalisé en utilisant du "beamforming". Le "Beamforming" est une technique qui consiste à adapter les antennes d'un noeud pour que la zone de couverture contienne un rayon plus long dans une direction choisie. L'adaptation de la zone de transmission et de réception dans une direction donnée est un des points clés de ce travail. Il, s'agit de concevoir comment les noeuds vont auto-organiser leurs rayons de couverture pour faciliter la diffusion des informations. Dans l'ensemble l'auteur a cherché à déterminer quelles améliorations des performances peuvent être obtenues dans les réseaux sans-fils, comment optimiser la vitesse de diffusion des informations dans le réseau, en minimisant l' "overhead".

Dans ce but, dans la section C.2 l'auteur suggère comment les informations locales et les modèles provenant de la nature comme la migration en groupe et l'inhibition latérale peuvent être utilisés pour accroître la vitesse de la diffusion des informations tout en maintenant un faible "overhead" dans un réseau statique. Dans la section C.2, l'auteur s'intéresse surtout au déploiement non uniforme de de la région. Cette règle limite le nombre de noeuds qui créent un faisceau. Les résultats montrent que l'algorithme améliore les performances du réseau en diminuant la longueur moyenne des chemins et le coefficient de clusterisation mais aussi améliore la connectivité.

  2, l'auteur a proposé l'utilisation de la mesure de la centralité avec d'autres concepts pour résoudre le problème dans le cas statique. Les concepts utilisés dans la section C.2 ne peuvent pas être appliqués au cas dynamique parce que le calcul de la mesure de la centralité deviendrait complexe, dépenserait beaucoup d'énergie et nécessiterait une informations sur l'historique[START_REF] Kim | Temporal Node Centrality in Complex Networks[END_REF][START_REF] Kim | Centrality Prediction in Dynamic Human Contact Networks[END_REF]. Sauvegarder une énorme quantité d'informations historiques dans un noeud dont la capacité mémoire est limitée poserait des problèmes informatiques. Dans ce but, l'auteur propose de calculer une mesure de stabilité des noeuds à l'instant t + ∆t en utilisant leur degré (mesure locale) à l'instant t pour améliorer la diffusion des informations. Dans[START_REF] Hanson | Perspectives on the Geographic Stability and Mobility of People in Cities[END_REF] il a été remarqué que la stabilité d'un noeud dans un graphe est étroitement reliée à la mobilité du noeud.Si on considère le degré, si un noeud a une stabilité de p% cela signifie que le noeud a conservé p% de son voisinage initial. Si p → 1 cela signifie que le voisinage du noeud n'a pas changé et qu'il ne communique qu'avec ses voisins. Cependant si p → 0, cela signifie d'abord que le noeud a un voisinage complètement différent de son voisinage initial et d'autre part que le noeud envoyait des informations à ses voisins à l'instant t et sera capable de recevoir des informations en provenance de nouveaux voisins t + ∆t. Par conséquent, il recevra les informations d'un plus grand ensemble de noeuds (voisinage à t et à t + ∆t) et de plus le noeud était déconnecté à l'instant t.Une méthode pour calculer la stabilité est proposée dans[START_REF] Brust | Heuristics on Link Stability in Ad Hoc Networks[END_REF] où les auteurs utilisaient le degré du noeud observé au cours de successifs instantanés. Dans un scenario mobile, où le "beamforming" est appliqué aussi, le calcul de la stabilité proposé par[START_REF] Brust | Heuristics on Link Stability in Ad Hoc Networks[END_REF] nécessiterait de connaître le nouveau

Self* refers to self organized, self similar, self configure, self manage, self adapt, self diagnose, self protect and self repair

GSCC in a directed graph is a component where there is a path between every pair of vertices.

GIN is the set of nodes in the component which can connect to GSCC.

A movie showing the dissemination process in Ivory Coast using the model can be viewed from http://complex. luxbulb.org/content/d4d-challenge

A movie showing the dissemination process in Ivory Coast using the model can be viewed from http://complex. luxbulb.org/content/d4d-challenge

auto* se rapporte à auto-organisation, auto-similarité, auto-configuration, auto-gestion, auto-adaptation, autodiagnostic, auto-réparation, auto-protection, auto-réparation

xxii Dr. Faiz Hamid for helping me both technically and socially during the course of my thesis. Further, I wish to thank the following people Prof. Emeritus Pierre Becker for his hospitality and being my tour guide during my frequent visits to Prof. Monique Beckers' home, Prof. Prem Kumar Kalra for getting me introduced to Prof. Monique Becker. I thank Prof. Emeritus Timothy Goldsmith of Yale, Prof. Elizabeth Wilmer of Oberlin College, Prof. Dan Braha of MIT, Prof. Yaneer Bar Yam of NECSI, Dr. Kristina Talbert-Slagle of Yale for providing me an opportunity to work with them during my NECSI days. Of course, I am grateful to my father and sister for their patience and love, without them this work would never have come into existence. Evry, France Rachit Agarwal DATE 2 nd September 2013

Enhancing Information Dissemination in Dynamic Wireless Network using Stability and Beamforming

Recent studies have shown that mobility can both speed up as well as slow down the dissemination process [START_REF] Kleinberg | Computing: The Wireless Epidemic[END_REF][START_REF] Schwarzkopf | Epidemic Spreading in Evolving Networks[END_REF][START_REF] Bajardi | Human Mobility Networks, Travel Restrictions, and the Global Spread of 2009 H1N1 Pandemic[END_REF][START_REF] Kivelä | Multiscale Analysis of Spreading in a Large Communication Network[END_REF]. The speed up in the dissemination process results from the increased probability of devices meeting each other causing more exchanges of data and thereby enhancing the dissemination. However, mobility can also adversely affect the rate of dissemination if it causes devices to get isolated quickly. A scenario where isolation can happen is when the node density is low. In such scenarios, the likelihood of devices exchanging information is reduced due to few instances of meeting.

However, in a mobile communication network, such as Mobile Ad hoc NETwork (M AN ET ),

Pocket Switched Networks (P SN ) and Delay Tolerant Networks (DT N ), we are interested in studying how information could be quickly transmitted through these time varying networks. Example scenarios can involve dissemination of traffic updates, which may not only involve single source of information but can also consist of emergency alerts and safety information generated from multiple sources. Key aspects of mobile communication network are that the communication is based on the contacts between the energy and memory limited devices. Further, information about the network is typically limited to that of the immediate neighborhood. This motivates us to study how information could be quickly transmitted through these time varying networks where devices lack global knowledge of the network, have limited energy and memory.

Networks characterized by high dynamicity have been the studied using Time Varying Networks.

A Time Varying Network is characterized as a network where the contacts between the devices are 77

Enhancing Information Dissemination in Device to Device Metapopulation using Human Mobility Trace and Beamforming

In communication networks devices in each other's physical proximity can communicate. Information dissemination in such proximity based networks have been the focus of a lot of studies. Through this Chapter, we are interested in how safety information can be quickly disseminated in a countrywide network with the help of Device-to-Device (D2D) communication. D2D communication is defined as a short range communication between devices in physical proximity without any involvement of the network infrastructure. D2D has many advantages like, autonomous communication, improved performance and spectrum reuse, low energy consumption and reduced load on the infrastructure.

Since, the interest lies in the dissemination process on a countrywide scale, mean field approximation is best suited to model the dissemination process in the contact network within the country. The information dissemination process can be closely related to the study of epidemic spreading across the population through Susceptible-Infected-Recovered (SIR) model. A comprehensive survey about the epidemic model is provided in [START_REF] Hethcote | The Mathematics of Infectious Diseases[END_REF][START_REF] Britton | Stochastic Epidemic Models: A Survey[END_REF]. In the context of message dissemination in a communication network, the S (Susceptible), I (Infected) and R (Recovered) states correspond to the state of a device 'not having the message', 'having the message and ready to transmit' and 'having the message but no longer willing to transmit the message to other devices to save energy', respectively.

In this context, it has been shown that information dissemination is influenced by many factors like communities in the network, bursty data [START_REF] Karsai | Small but Slow World: How Network Topology and Burstiness Slow Down Spreading[END_REF], strength of the connection [START_REF] Miritello | Dynamical Strength of Social Ties in Information Spreading[END_REF], source of the infection, human mobility parameters (Chapter 4), location preferences [START_REF] Wang | Safety-Information-Driven Human Mobility Patterns with Metapopulation Epidemic Dynamics[END_REF], network structure [START_REF] Nicosia | Impact of Network Structure on a Model of Diffusion and Competitive Interaction[END_REF], activity pattern [START_REF] Vazquez | Impact of Non-Poissonian Activity Patterns on Spreading Processes[END_REF], altruism [START_REF] Hui | Selfishness, Altruism and Message Spreading in Mobile Social Networks[END_REF], social measures [START_REF] Keeling | Networks and Epidemic Models[END_REF], antenna parameters as discussed (shown by small circles inside big circles). Moreover, this can be generalized to |C| communities. This type of mobility model is a simple depiction of the inter-community movements. However, the mobility model can be enriched by including the information of home location for each node. A model introducing the return rates in this simple mobility model is described in the Section 5.3.5.

We assume that the behavior of one device is Markovian. For N devices, the superposition of these Markov processes is Markovian. It leads to a Continuous Time Markov Chain (CT M C).

Due to mobility, the number of the devices in a community i change. This change in the number of devices in a community is defined as

In eq. 5.3.1, the term ∀j∈C,j =i σ j ν ji N j represents the number of devices coming to the community i. However, the term ∀j∈C,j =i σ i ν ij N i represents the number of devices going out of community i. Using the definition 5.3.2, the eq. 5.3.1 can be represented as

In order to visualize the dissemination process, we first identify the steady state of the mobility model. Note that there are two models, mobility model and dissemination model. For the mobility model, we look for the steady state limit solution. Let N * i be the steady state population in community i. Note that N * i is a limit and will not change over time. Then, we use the differential equations in order to derive the transient solution for the dissemination process where we study the change in the number of devices in S, I and R state. In the differential equations, we use the parameters that are derived from a mean field approximation and do not change over time. However, note that the number of devices in state S, I and R will change over time.

Further, note that, the steady state does not mean that the devices are not moving out of a community or the devices are not coming in to the same community. It only states that the expected number of devices in a community does not change over time, i.e. expected number of devices coming in to a community is equal to the expected number of devices moving out of the same community.

At the steady state, dNi dt = 0 for all i ∈ C. The steady state population in the community i, N * i , rate equation for the change in number of devices in state S, I, R, E S , E I and E R is defined as

To see a positive effect of beamforming a necessary condition is k i < k * i which reduces to k i < k X,i . This means that k X,i for a beamforming device should be greater than k i for the same device when it was not beamforming. Let the current beamforming scenario be case B ′ . Let I i,t,B ′ and I i,t,B be the number of devices in state I in the community i at time t for case B ′ and B respectively. The difference in the number of devices in state I at time t for B ′ and B for all the communities on the population scale is defined as

(5.3.7)

When the initial condition is same as defined before. Then I i,0,B ′ = I i,0,B .

Mobility Model with Return Rate

In this Subsection, we enrich the mobility model presented in Section 5.3.1 by considering rate of return to home community for each device [START_REF] Sattenspiel | A Structured Epidemic Model Incorporating Geographic Mobility among Regions[END_REF][START_REF] Belik | Natural Human Mobility Patterns and Spatial Spread of Infectious Diseases[END_REF]. Let N ii be the number of devices having home community as i that are in community i and N ij be the number of devices having home community as i that are in community j. As defined in definition 5.3.1 and 5.3.2, let σ i be the rate of moving out of community i and ν ij as the conditional probability of going to community j given the dive has moved out from community i, respectively.

Definition 5.3.9. For a device, the rate to return to its home community i from community j is defined as ζ ji = (M RR c ) ji . Note that when ζ ji → ∞, it means that the device returns to its home

0 for all communities. In order to start the dissemination, we set S 0 = N * iε and I 0 = ε where ε → 0. In D2D communication scenario, this means that a public warning message is generated somewhere in the area covered by eN B having ID equal to 0. Through the evolution of fraction of devices in any of the three states, in this Chapter, we show the effect of the model on the dissemination of the

A.1.1 Wireless Flow Betweenness

In wireless ad hoc networks, the computation costs are particularly costly because of the transmission overheads involved. In order to ensure that network performance is not affected, thus, the computation of a betweenness measure should ideally incur zero overheads. Using this as the motivation, We propose a measure of betweenness computed by nodes by exploiting the wireless broadcast advantage (W BA), thereby minimizing the overheads incurred.

The proposed measure W F B, makes use of information extracted from traffic flows being routed through the network to estimate the structural importance of nodes in the network. This allows the computed measure of centrality to adapt to the traffic flow patterns in the network. Further, traffic flow information can be obtained locally by nodes, thereby minimizing the transmission overheads.

Finally, such a mechanism can proceed in parallel with regular network operations such as routing and packet delivery, therefore increasing its robustness. After starting off with a simplistic expression of locally computable centrality we identify the redundancies involved in such a measure and describes how they are addressed.

The broadcast nature of the wireless medium results in implicit sharing of information as nodes can overhear all transmissions in their one-hop neighborhood. Based on this neighborhood information, a node estimates its importance in terms of how often it transmits its information, either as a source or as a forwarding node. Consider a network G(V, E) with set of nodes V and set of edges E.

Let g(u) denotes the number of packets forwarded by a node u ∈ V for distinct source-destination pairs while N (v) denotes the set of neighbors of v ∈ V . A straightforward measure of betweenness of a node v, can therefore be computed as the ratio of the number of times it acts as a forwarding node to the total number of unique traffic flows in its neighborhood. This can be expressed as

The denominator in the eq. A.1.1 gives the total number of packets forwarded in the neighborhood of v. The eq. A.1.1, though straightforward in design, only gives an egocentric measure of importance of the node v. This is because a count of the transmissions in the neighborhood does not give any indication of the likelihood of any flow in the network passing through v. Identifying the exact number of traffic flows in the entire network, including those that do not pass through However, the above summation over all neighbors of v introduces a second redundancy which needs to be taken care of. Just as v is aware of all packets transmitted by a neighbor u, multiple neighbors of v also affect each other's betweenness values. Neighbors of v which are also neighbors of each other estimate the term a f based on the values of w observed for each other. Consider two nodes u and u ′ which are neighbors of v as well as neighbors of each other. As part of their centrality calculations, u and u ′ estimate a f (u ′ ) and a f (u) respectively. Both these values include the number of transmissions made by v. In the absence of a one-hop neighborhood map, neither node is aware of v being a common neighbor and therefore, a f (v) is implicitly counted more than once, resulting in overestimation of the number of flows at all the three nodes. This effect is aggravated over multiple iterations and for networks with high node density.

In order to handle the second redundancy, the set of neighbors whose betweenness values are used for computation is limited. Nodes that infrequently act as forwarding nodes spend the majority of time overhearing transmission from other nodes. Computing the a f measure for such a flow is likely to result in a lot of redundancy as the majority of estimated additional flows are likely to be redundant. Thus, a the definition of W F B is revised to only consider the neighbor which acts as a forwarding node most often. The possibility of redundancy is reduced with such a choice as the node chosen is unique within a neighborhood. Further, since a majority of traffic in a given network region flows through this node, it gives a better estimate of the number of flows. Based on this discussion, the W F B value of a node v is obtained as

where u = arg max

A node computes its W F B value whenever it acts as a forwarding node or overhears a transmission in its neighborhood.

By considering a single node in the neighborhood, the chances of overestimation are reduced.

However, it also raises the possibility of some flows not being counted. Looking at the denominator of the expression in (A.1.3), it is observed, as before, that the term o(v) accounts for all transmissions in the neighborhood of v, and therefore includes g(u). Thus, the term ( g(u) w(u) -g(u)) gives the number of additional flows in the network estimated recursively. As with node v, the value of w(u) takes where V is the set of all nodes in the network and d i is the absolute difference in rank between the two rankings for the i th node. A value ρ = 1 implies perfect correlation between the two rankings.

A.1.3 Overhead and Buffer Costs

While the above results show that there is a close correlation between the W F B values computed at individual nodes and the corresponding F BC values, it is necessary to understand the additional costs required for such computation.

The transmission overhead costs are minimal since only W F B values are piggy-backed on to packets by the forwarding nodes, involving one additional field. Thus, additional transmission costs are of constant order. The design, however, requires nodes to store the W F B values of their neighbors along with the corresponding forwarding count. The buffer requirements, thus, scale with increase in the node density. Given a neighborhood size of n nodes, a node needs to store three fields for each neighbor, namely the node identity along with the W F B value and the forwarding count, resulting in a buffer size of the order of O(3n). However, since a lot of existing ad hoc network mechanisms rely on the presence of neighborhood knowledge, which is of O(n), the additional costs involved for computation of W F B are unlikely to impose a significant burden.

A.1.4 Using W F B for Small World Creation with Beamforming

We now explore the use of W F B for small world creation using directional beamforming. Motivated by the close correlation between W F B and F BC, we evaluate the performance benefits of using