Statistics
| Branch: | Revision:

## root / thesis / ch1_introduction.tex @ df1b1a42

 1 %!TEX root = main.tex  \chapter{Introduction}   People have a strong need for acquiring information. The faster, the more reliable, the more secured way, the more affordable mean to communicate, the better that communication technique is. During the 90s we have seen the boom of the Internet, at that time most devices was connected to the Internet through a cable with an ISP standing in between to provide services. In the late 2000s, connecting to the Internet without plugging anything in had became a norm. Most of the wireless networks that we are familiar with now such as 3G, LTE, 4G, Wi-Fi, they are centralized network, which means those networks rely on the base stations to broadcast signal, or access points in a managed wireless network to provide the service. And then, \textbf{XXX any year?}, Wireless Mesh Networks (WMNs) have merged as a key technology for next-generation wireless networking.   We begin, in this introductory chapter with the short overview of WMNs in \cref{sec:introduction_wmns}. Then we will present one application of WMNs in reality - the Wireless Community Networks (WCNs). We will cover the definition plus some challenging problems of WCNs in \cref{sec:introduction_wcns}. The chapter ends with the contribution, and the outline of the thesis.  \section{Wireless Mesh Networks} \label{sec:introduction_wmns}   Wireless Mesh Network (WMN) is any wireless network having a network topology of either a partial or full mesh topology \cite{zhang2006wireless}. In full mesh topology, every pair of nodes is directly connected with each other, while in partial mesh topology, not all nodes are directly interconnected with each other by other nodes. Eventhough the definition of WMN mentions the full mesh topology, in practice, WMN is usually built over a partial mesh topology. This is due to the limited coverage of signal from wireless devices making it impossible for each node to directly conect with all other nodes.   For classification, WMNs belong to a category of multi-hop wireless network, where information traverses from a source to a destination using two or more wireless hops.   The main advantages of a WMN is its capability of fault intolerance. Since WMN is a decentralized wireless network, when several nodes is taking down, the network can find a new path way to link the network together. The term \emph{autonomic system} is normally used to describe properties of WMN.   WMN has several properties:   \begin{itemize}   \item Self-forming   \item Self healing   \item Self optimization   \item Multi hop   \end{itemize}   WMNs find a great applications in many areas \citep{Akyildiz2005445} such as: broadband home networking, enterprise networking, community networking, city-wide wireless coverage, spontaneous mesh network, transporation systems. However, all different areas for application can be classified into 2 categories. Firstly, WMN acts as a backbone network to extend the Internet connectivity for nodes that are not in the coverage of Internet access. This might due to the fact that installing wired infrastructure is too expensive for rural areas, or areas with challenging terrains. Another scenario is in a diaster-stroke area where the current communication facilities (cables, base stations) were destroyed, then WMNs can provide temporary solution for communication. Secondly, WMNs is used to enable the communication between nodes within the mesh network.   For the first category - extending the Internet connectivity, there are many examples on its usage in reality. It has been used in Dharamsala \citep{jardin2006} to provide internet access for refugee monks living in the mountainous area in Dharamsala. \cite{Suzuki2006} introduced \emph{SKYMESH} to provide Internet access in a disaster area. It use helium-filled balloons carrying WiFi transceivers, and together they form the mesh network.   The second usage of WMNs focus on the communication within the network. For example, in transportation management, \cite{Ahmed2008} proposed a prototype using wireless mesh networks to help with monitoring traffic. The car has sensors to collect data, and the real-time data is gathered using the WMN. Wireless Community Networks are another applications of WMNs, where a group of local users set up and manage a network for themselves. WCNs can have a gateway (or not) to the Internet. This WCNs will be discussed more in \cref{sec:introduction_wcns}.  \section{Wireless Community Networks} \label{sec:introduction_wcns}  Application:   Wireless Community Network (WCN) \cite{Jain2003} belongs to wireless mesh network. It also servers 2 purposes as WMN: to provide internet access for those nodes which do not have it, and to create an environment for communication that offer higher privacy.   What  http://www.npr.org/2006/08/10/5631353/a-wireless-network-for-little-lhasa   \cite{Maccari2015175} presented an argument that closeness centrality can be used  \section{Contributions of this thesis} \label{sec:introduction_contribution}   In graph theory, centrality metrics (which will be explored in depth in \cref{sec:centrality}) is used to determine how influential a node is in the network. \cite{Katsaros2010} presented two types of centrality metrics that he considered them to have significant applications in analysing wireless networks. They are degree based centrality, and shortest-path based centrality.   \cite{Maccari2015175} proposed to use \emph{closeness group centrality} $C_C(\gamma)$ - one type of degree based centrality - to identify the central group in the WCNs. $\gamma$ is a group of nodes. Knowing the central group, the group with the lowest $C_C(\gamma)$ can be useful in, for example, determining where to place the Internet gateway. Suppose that this WCNs is designed to provide Internet access for its client, then the most central group will give the best average Internet connectivity to the nodes in the network.   The type of centrality metrics to choose will depend on the purpose of analysis. \cite{Maccari2014670} also mentioned shortest-path based centrality $C_sp(k)$ should be employed when we want choose a set of nodes that have control a fraction $\eta$ of the entire traffic of the network. \citeauthor{Maccari2014670} gave 3 scenarios on why knowing betweenness centrality would help in resolving those 3 problems. Given that WCNs is not a static network, nodes can come and leave the network as they wish. Therefore, the betweenness centrality would change over time. Moreover, routers do not have enough computational power to excecute complex algorithm. Therefore, to make it feasible for WCNs to detect the set of most influential nodes, the algorithm must run fast enough \textbf{XXX how fast?} on the computationally limited physical device.   In this thesis, I test out the performance of shortest-path based betweenness centrality (from now on it will only be called \emph{betweenness centrality} algorithm on the real router. The state-of-the-art for calculating betweenness centrality is $\mathcal{O}(mn + n^2 \log n)$ \citep{Brandes01afaster}. Eventhough it is a huge improvement comparing to $\mathcal{O}(n^3)$, it is still not feasible to compute that centrality for large graph. The second algorithm is the heuristic-based by \cite{PuzisZEDB12}. This algorithm follow a divide-and-conquer design paradigm, the network is divided into bi-connected components. Betweenness centrality is calculated for each bi-connected components with a little bit of modification, and then they are summed up to achieve the same result as the state-of-the-art algorithm. The presentation of both algorithms can be found in \cref{sec:computation_betweenness}   Since the algorithm of \citeauthor{PuzisZEDB12} is a heuristic-based, there is no guarantee on the running time. Therefore, I carry out an extensive experiments to compare 2 algorithms. The experiment is run on random graphs: Erdos, Power Law, Community Network \footnote{This is not the real wireless community networks, but the generation algorithm was designed such that the topology is similar to the topology found in WCNs}. And the performance is measured in the virtualized environment with QEMU \footnote{http://wiki.qemu.org}, and on the real router.   This is the first time that both algorithms of betweenness centrality has been tested on the real device.  \section{Outline of this thesis} \label{sec:introduction_outline}   The outline of this paper is as follows. The first two chapters cover all the necessasry background information. Section \cref{sec:centrality} examines the concept of centrality. Since there are numereous measures for centrality, only those centrality measures that are most relevant will be presented. And betweenness centrality will be discussed in deep. Section \cref{sec:computation_betweenness} presents 2 algorithms to calculate the exact betweenness.   The next two chapters deals with the setting up and results of the simulation. Details on the dataset, repetition will be provided in \cref{sec:sim_scenario}. \cref{sec:sim_experiment} summarises the result of the simulation.  \clearpage  \section{Scope}   The scope of the paper:   \begin{itemize}   \item no self-loop   \item no multigraph: graph with no parallel edges   \item unweighted and weighted graph   \item can apply to connected or disconnected graph. In the disconnected graph, certain vertices are not reachable from vertices in a different component. This yeilds the zero shortest paths counts, and as a result those 2 endpoints contributes 0 toward the betweenness.   \end{itemize}   connected graph: since the betweenness centrality is calculated based on shortest paths. In the disconnected graph, certain vertices are not reachable from vertices in a different component. This yields the zero shortest paths counts for betweenness centrality.  \section{Notation}   A graph $G=(V,E)$ contains a set of vertices (nodes) $V$ and a set of edges (links) $E$. We assume we assume that al graphs are undirected and connected. \textbf{XXX check the modification for directed graph}   $m = |E|$ is the number of edges in graph $G$   $n = |V|$ is the number of vertices in graph $G$   Let $\omega$ be a weight function on the edges. We assume that $\omega(e) > 0, e \in E$ for weighted graphs. And we define $\omega(e) = 1, e \in E$ for unweighted graphs. If for $s, t \in V$ and ${s, t} \in E$, then we can also use $\omega(s, t)$ to denote the weight of the edge between $s$ and $t$.   The \emph{length} of a path is the sum of weights of all edges along the path. We use $d(s, t)$ to denote the \emph{distance} between vertices $s$ and $t$, i.e. the minimum length of any path connecting $s$ and $t$.