## 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} |