Statistics
| Branch: | Revision:

root / thesis / ideas.tex @ c6e2ce5a

History | View | Annotate | Download (16.4 KB)

1
\usepackage[colorlinks]{hyperref}       % from http://tex.stackexchange.com/questions/3568/how-does-one-typeset-a-url
2
\hypersetup{citecolor=green}
3
\hypersetup{linkcolor=red}
4
\hypersetup{urlcolor=blue}
5

    
6
\documentclass[12pt]{article}
7
\begin{document}
8

    
9
\title{Thesis}
10

    
11
\author{Quynh Nguyen - DISI - University of Trento}
12

    
13
\maketitle
14
\clearpage
15

    
16
This document contains writing/summary from books/papers.
17

    
18
\section{How to write thesis}
19
    \href{https://crawfordphd.wikispaces.com/Writing+your+thesis+introduction,+conclusion,+and+abstract}{Crawford PhD}
20

    
21
    \href{http://jameshaytonphd.com/leaving-your-thesis-introduction-till-last-it-could-be-a-mistake/}{James Hayton PhD}
22
    \section{Introduction}
23
        You have to find a way of giving them the big picture before the deep context.
24
        \begin{itemize}
25
            \item Intrduction to the introduction: 3 paragraphs.
26
            \item Context: give the full context
27
            \item Restatement of the problem.
28
        \end{itemize}
29

    
30
\section{Paper Summary}
31
    \section{Newman 2005}
32
        Paper: \cite{Newman200539}
33

    
34
    \section{Barthelemy 2004}
35
        Paper: \cite{Barthelemy2004}
36

    
37
        Introduction: not all nodes are equivalent. Some nodes are more important than the others. Then the problem is how to assign the important score for each node. Give example of the node resilience to attacks.
38

    
39
    \section{Kas 2013}
40
        Paper: \cite{Kas:2013:IAU:2492517.2492533}
41
        I can learn from this paper how to structure the \textbf{Computation of BC} section.
42

    
43
\section{Introduction}
44
    \subsection{Current Mesh Network}
45
        Freifunk
46
        GuiFi
47
    \subsection{The problem of Mesh Network}
48
    Technical challenge: latency [http://www.wired.com/2014/01/its-time-to-take-mesh-networks-seriously-and-not-just-for-the-reasons-you-think/]
49
    \begin{itemize}
50
        \item Routing protocols are currently unable to scale over a few hundred nodes
51
        \item Network coverage is constrained by the limited range of wireless user devices.
52
    \end{itemize}
53

    
54
        "Compared to traditional mobile ad hoc networks (MANETs), wireless sensor networks (WSNs), and infrastructure-based mobile cellular networks, WMNs are quasi-static in network topology and architecture, have fewer resource constraints at the mesh routers, and are easy and flexible to deploy with lower costs."
55

    
56
        "Potential applications of WMNs include broad- band home networking, community and neighborhood net- working, enterprise networking, building automation, health and medical systems, public safety and security systems, intelli- gent transportation systems, emergency/disaster networking, metropolitan area broadband Internet access, and so on. This wide range of applications and services has different technical requirements and challenges in the design and deployment of mesh networking architectures, algorithms, and protocols."
57

    
58
            The need for communication is huge.
59
    Ability to communicate when a disaster stroke is really helpful to distributing aids and supports.
60
    The next generation of wireless network is moving towards a decentralized central network.
61

    
62
    divergence from the traditional centralized wireless systems
63

    
64
    How communication happens? ==> Over the internet
65

    
66

    
67
    Community Network is one application of WMN.
68

    
69
    Legal challenges
70

    
71
    WMN distinguishes itself from traditional wireless network such as WLAN has properties of an \emph{autonomic system}.
72

    
73
        Wireless Mesh Network, in the most simple term, is a multi-hop network built from wireless routers} and has a properties of an \emph{autonomic system}. WMN belongs to
74

    
75
        http://www.csg.ethz.ch/education/lectures/ATCN/ws06_07/doc/WMN-BasicsWS0607.pdf
76

    
77
        "A mesh network is a local area network (LAN), wireless local area network (WLAN) or virtual LAN (VLAN) that employs one of two decentralized connection arrangements: full mesh topology or partial mesh topology. In a full mesh topology, each network node (workstation or other device) is connected directly to each of the others. In a partial mesh topology, some nodes are connected to all the others, but others are only connected to those nodes with which they exchange the most data." [http://internetofthingsagenda.techtarget.com/definition/mesh-network-topology-mesh-network]
78

    
79
        WMN is any wireless network having a network topology of either a partial or full mesh topology, practical WMNs are characterized by static wireless relay nodes providing a distributed infrastructure for mobile client nodes over a partial mesh topology. \cite{zhang2006wireless}
80

    
81
        IEEE Network: Special Issue about Wireless Mesh Network.
82
        http://ieeexplore.ieee.org/xpl/tocresult.jsp?isnumber=4435892
83

    
84
        researchers, as well as industry, believe wireless mesh networks to be a major factor in bringing networking access to the unteth- ered masses.
85

    
86

    
87
        Wireless mesh networks (WMNs) consist of mesh routers and mesh clients, where mesh routers have minimal mobility and form the backbone of WMNs. They provide network access for both mesh and conventional clients. The integration of WMNs with other networks such as the Internet, cellular, IEEE 802.11, IEEE 802.15, IEEE 802.16, sensor networks, etc., can be accomplished through the gateway and bridging functions in the mesh routers. Mesh clients can be either stationary or mobile, and can form a client mesh network among themselves and with mesh routers. WMNs are anticipated to resolve the limitations and to significantly improve the performance of ad hoc networks, wireless local area networks (WLANs), wireless personal area networks (WPANs), and wireless metropolitan area networks (WMANs). They are undergoing rapid progress and inspiring numerous deployments. WMNs will deliver wireless services for a large variety of applications in personal, local, campus, and metropolitan areas. Despite recent advances in wireless mesh networking, many research challenges remain in all protocol layers. This paper presents a detailed study on recent advances and open research issues in WMNs. System architectures and applications of WMNs are described, followed by discussing the critical factors influencing protocol design. Theoretical network capacity and the state-of-the-art protocols for WMNs are explored with an objective to point out a number of open research issues. Finally, testbeds, industrial practice, and current standard activities related to WMNs are highlighted. [http://dl.acm.org/citation.cfm?id=1071646]
88

    
89

    
90
        A wireless mesh network (WMN) is a mesh network implemented over a Wireless LAN (WLAN). In WMNs, communications between nodes and those between nodes and clients are over a radio link. [http://www.webopedia.com/TERM/W/wireless_mesh_network_WMN.html]
91

    
92
        http://www.csg.ethz.ch/education/lectures/ATCN/ws06_07/doc/WMN-BasicsWS0607.pdf
93

    
94
        A wireless mesh network is a \emph{multi-hop network built from wireless routers} and has a properties of an \emph{autonomic system}
95

    
96
        ad hoc networking --> WMN
97

    
98
        path selection metrics: hop count (not optimal), Expected Transmission Time, Expected Transmission Count, Weighted Cumulative ETT
99

    
100
        AODV: does this apply in our case?
101

    
102

    
103
=========
104
    I'm writing my thesis about the betweenness centrality.
105
    And that measurement comes from social analysis.
106

    
107
    The Mesh Network, and their problems (latency). Latency is caused by the routing protocols. So if we can improve the routing protocol, then we suspect that the latency in the Mesh Network can be reduced.
108

    
109

    
110
    \section{Move 1: Introduce the filed/context}
111

    
112
    \section{Move 2: Uncover the full context}
113

    
114
    \section{Move 3: Define a research problem - Motivation}
115
        What is the problem? Running the heuristic version to calculate BC score on the router.
116

    
117
        Why do we want to pursue this research? Why your research matters? Why anyone would want to read about it?
118

    
119
        What do I hope to explore / establish?
120

    
121
        ? Anyone use BC in routing?
122

    
123
\section{Centrality}
124
    General --> Detail --> General: Centrality indices --> shortest-path based centrality --> stress centrality --> shortest-path betweenness centrality
125

    
126
    \section{Centrality}
127
        Centrality index is required to only demanding on the structure of the graph. [XXX check out Def. 3.2.1 in \cite{Brandes:2005:NAM:1062400}]
128

    
129
        Purpose of centrality:
130
            \begin{itemize}
131
                \item Core concept for the analysis of social networks
132
                \item help analyze networks and the situation these networks represent.
133
            \end{itemize}
134

    
135
        There are many types of centrality indicies:
136

    
137
    \section{Shortest-path based centrality}
138
        Betweennes centrality indicies belongs to one class of centrality indices
139

    
140
    \section{Shortest-path Betweenness Centrality}
141
        $c_B(v)$ can be interpreted as the extent to which vertex $v$ can controls the communication between each pair of end vertices.
142

    
143

    
144

    
145
    \cite{Freeman1977} introduces a set of measures of centrality
146

    
147
\section{Betweenness centrality}
148
    Why do people use betweenness centrality?
149
    \begin{itemize}
150
        \item Eventhough not all communication go through the shortest path, in the network, we can assume that all the traffic will use the most efficient way to reach the destination.
151
        \item
152
    \end{itemize}
153

    
154
    What is the role of betweenness centrality in network communication?
155

    
156
    \textbf{XXX Define betweenness --> partial betweenness}
157

    
158
            \cite{Freeman1977}  wrote a paper called ``A Set of Measures of Centrality Based on Betweenness'' to propose an alternative way to measure centrality that can address the unconnected network, while providing the meaning in communication terms. Freeman defined the concept of \emph{point centrality} as ``the potential of a point for control of information flow in the network.'' That paper laid the foundation for betweenness centrality by providing a general procedures for measuring it.
159

    
160
            The \emph{geodesics} path is the shortest path connecting 2 points $p_i$ and $p_j$. The point is considered to be central depending on the number of times that it lies on the geodesics communication paths.
161

    
162

    
163

    
164

    
165

    
166

    
167
            \cite{Freeman1991141} gave an excellent classification of centrality based on how
168

    
169
            Centrality can be measured for vertices or edges.
170

    
171
            In most network, some vertices are more central than the others. And those more central vertices are considered to have more effect on the flow of the network.
172

    
173
            Centrality is a measure arised from social network analysis. And there are many ways to calculate the centrality. In fact, the centrality ind
174

    
175

    
176

    
177

    
178
            The first classical vertex centrality indices were ivntroduced by
179

    
180
            "a vertex can be regarded
181
        as central if it is heavily required for the transport of information within the
182
        network or if it is connected to other important vertices." \cite{Brandes:2005:NAM:1062400}
183

    
184
        "The betweenness centrality does not suffer from this problem: Any pair of
185
        vertices s and t without any shortest path from s to t just will add zero to the
186
        betweenness centrality of every other vertex in the network."
187

    
188
        feel of
189

    
190
\section{Experiment setup}
191
 Cores is a hardware term that describes the number of independent central processing units in a single computing component (die or chip).
192

    
193
       A Thread, or thread of execution, is a software term for the basic ordered sequence of instructions that can be passed through or processed by a single CPU core.
194

    
195
       Intel® Hyper-Threading Technology (Intel® HT Technology) delivers two processing threads per physical core. Highly threaded applications can get more work done in parallel, completing tasks sooner.
196

    
197

    
198
\section{Questions}
199
What is \emph{ad hoc measure}?
200

    
201
status quo
202

    
203
\section{Words to use in report}
204
    \section{Verbs}
205
        constitute
206
        deploy
207
        jeopardize
208
        disrupt
209

    
210
    \section{Adjective}
211
        beneficial
212

    
213

    
214
    \section{Nouns}
215
        approach
216
        influential actors
217

    
218
\section{Skeleton}
219
    \section{Skeleton}
220
    Justify your work
221
    Introduce Wireless Mesh NEtwork, Community Network. CN is the special case of WMN.
222

    
223
    1 chapter explaining what is centrality
224
    * Mention the application of centrality to our application.
225
    * What we are doing here is different from the state of the art. It's the same algorithm, but we run on ... real platform, so that people can
226
    * And we want to do it in realtime, because there are couples of .... tune ....
227
    * Cite the paper from your supervisor.
228
    * Mc Cully paper.
229

    
230
    1 chapter explaining different algorithms used to calculate centrality.
231

    
232
    Then, 1 chapter about your work, technical chapter
233
    * Which problems have you faced?
234
    * Documentation code
235

    
236
    Then, 1 chapter about the result
237

    
238
    Bibliography: 20 - 3.0
239

    
240

    
241
\section{Scope}
242
        The scope of the paper:
243
        \begin{itemize}
244
            \item no self-loop
245
            \item no multigraph: graph with no parallel edges
246
            \item unweighted and weighted graph
247
            \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.
248
        \end{itemize}
249

    
250
    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.
251

    
252

    
253
\section{Notation}
254
    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}
255

    
256
    $m = |E|$ is the number of edges in graph $G$
257

    
258
    $n = |V|$ is the number of vertices in graph $G$
259

    
260
    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$.
261

    
262
    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$.
263

    
264
\section{Result}
265

    
266
        \begin{figure}[h]
267
        \caption{}
268
        \label{fig:histogram_num_of_nodes_CN200}
269
        \centering
270
        \includegraphics[scale=0.6]{images/histogram_num_of_nodes_CN200.png}
271
        \end{figure}
272

    
273
        \begin{figure}[h]
274
        \caption{}
275
        \label{fig:histogram_num_of_nodes_ER200}
276
        \centering
277
        \includegraphics[scale=0.6]{images/histogram_num_of_nodes_ER200.png}
278
        \end{figure}
279

    
280
        \begin{figure}[h]
281
        \caption{}
282
        \label{fig:histogram_num_of_nodes_PL200}
283
        \centering
284
        \includegraphics[scale=0.6]{images/histogram_num_of_nodes_PL200.png}
285
        \end{figure}
286

    
287

    
288
\section{Counting shortest paths}
289
    In the end, I choose not to describe those algorithms in the final version of my thesis
290

    
291
    \textbf{XXX What is the input}: the source vertex $s$
292
        \textbf{XXX What is the output?}:
293

    
294
        \subsection{Breadth-First Search for unweighted graph}
295
            I understood the algorithm, but how can I explain it to another person?
296

    
297

    
298

    
299
        \subsection{Dijkstra's algorithm for weighted graph}
300
            The Dijkstra's algorithm can be modified so that when given a source vertex $s$, the output will be the set of predecessors and the number of shortest paths from $s$ to other $t \neq s \in V$
301

    
302
            \begin{algorithm}
303
            \caption{Dijkstra's algorithm} \label{algo:dijkstra}
304
            \begin{algorithmic}[1]
305
                \Procedure{Dijkstra for SSSP with source vertex s}{}
306
                    \State $S \leftarrow$ empty stack
307
                    \State $P[w] \leftarrow$ empty list, $w \in V$
308
                    \State $\sigma[t] \leftarrow 0, t \in V$; $\sigma[s] \leftarrow 1$
309
                    \State $d[t] \leftarrow -1, t \in V$; $d[s] \leftarrow 0$
310
                    \State $Q \leftarrow $ empty queue
311
                    \State enqueue $s \rightarrow Q$
312
                    \While{$Q$ \emph{not empty}}
313
                        dequeue $v \leftarrow Q$
314
                        push $v \rightarrow S$
315

    
316
                    \EndWhile
317
                \EndProcedure
318
            \end{algorithmic}
319
            \end{algorithm}
320

    
321
\clearpage
322
\bibliography{references}{}
323
\bibliographystyle{plain}
324

    
325
\end{document}