Tags:
create new tag
view all tags

Program and Textbooks/ Programma del corso e Testi

English


Here the general topics that will be dealt with during the course are listed. For a deeper detail, please go to the Lesson Diary.
0. Introduction to the Course

1. cable networks

1.1. The Routing problem i.e. the minimum cost shortest path

References:

Student lessons:

For a thorough examination of the topic:

  • Dynamic routing algorithms for interconnection topologies

1.2. The layout of interconnection networks i.e. the orthogonal grid graph drawing

References:

Student lessons:

For a thorough examination of the topic:


1.3. The problem of infecting a network with a worm i.e. the minimum vertex cover problem

References:

Student lessons:


1.4. The problem of minimizing a boolean circuit i.e. the minimum set covering problem

References:

Student lessons:


2. wireless ad hoc networks

2.1. The frequency assignment problem i.e. a graph coloring problem

References:

Student lessons:

For a thorough examination of the topic:


2.2. The minimum energy broadcast problem i.e. the minimum spanning tree problem

References:

Student lessons:

For a thorough examination of the topic:

  • Approximation bound of 6 by Ambüehl

2.3. The data mule scheduling problem i.e. the travelling salesman problem

References:

Student lessons:


3.mobile sensor networks

3.1. The centralized deployment of a mobile sensor network i.e. the minimum cost perfect matching in bipartite graphs

References:

Student lessons:

For a thorough examination of the topic:


3.2. Self-deployment of a mobile sensor network i.e. the Voronoi Diagram

References:

Student lessons:

For a thorough examination of the topic:

3.3. Monitoring by UAVs i.e. What? (some theses proposals)

Student lessons:


Italiano


Si riportano qui gli argomenti orientativi che si intende affrontare durante il corso ed i riferimenti per studiare. Per un maggior dettaglio sugli argomenti effettivamente svolti si rimanda al diario delle lezioni.
0. Introduzione al corso

1. reti cablate

1.1. Il problema dell'instradamento ovvero il problema della ricerca del cammino più corto di costo minimo (pesi pari al costo o alla probabilità di guasto della connessione)

Riferimenti per studiare:

Tesine:

Possibili approfondimenti:

  • algoritmi di instradamento dinamici per topologie di interconnessione

1.2. Il problema del layout di topologie di interconnessione ovvero il problema del disegno ortogonale su griglia

Riferimenti per studiare:

Tesine:

Possibili approfondimenti:


1.3. Il problema di infettare (e difendere) una rete con un worm ovvero il problema della minima copertura di vertici

Riferimenti per studiare:

Tesine:


1.4. Il problema di minimizzare un circuito booleano ovvero il problema della minima copertura di insiemi

Riferimenti per studiare:

Tesine:


2. reti wireless ad hoc/wireless ad hoc networks

2.1. Il problema dell'assegnazione di frequenze ovvero un problema di colorazione di grafi

Riferimenti per studiare:

Tesine:

Possibili approfondimenti:


2.2. Il problema del broadcast con minimo dispendio di energia ovvero il problema del minimo albero ricoprente

Riferimenti per studiare:

Tesine:

Possibili approfondimenti:

  • Bound di approssimazione di 6 di Ambüehl

2.3. Il problema del data mule ovvero il problema del commesso viaggiatore

Riferimenti per studiare:

Tesine:


3. reti di sensori mobili

3.1. Il problema del dispiegamento centralizzato di sensori mobili ovvero il problema dell'accoppiamento perfetto di costo minimo su grafo bipartito

Riferimenti per studiare:

Tesine:

Possibili approfondimenti:


3.2. Il problema del dispiegamento distribuito di sensori mobili ovvero il problema del diagramma di Voronoi

Riferimenti per studiare:

Tesine:

Possibili approfondimenti:

3.3. Monitorare tramite UAVs ovvero Cosa? (alcune proposte di tesi)

Tesine:


Bibliografia/Bibliography

Libri/Books

  • [CZ] G. Chartrand, P. Zhang, Chromatic Graph Theory, CRC Press 2009.
  • [CLRS] T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms and Data Structures, Mc Graw-Hill 2001.
  • [GYnero] J.L. Gross, J. Yellen, Graph Theory and its applications, Chapman & Hall 2006.
  • [GYrosso] J.L. Gross, J. Yellen, Handbook of Graph Theory, CRC Press 2004
  • [J] D. Jungnickel, Graphs, Networks and Algoritthms, Springer, 2005.
  • [L] F.T.Leighton, Introduction to parallel algorithms and architectures: array, trees, hypercubes, 1991.

Articoli/Papers

  • [Aal15] C. Archetti, N. Bianchessi, A. Hertz, A. Colombet, F. Gagnon, "Directed weighted improper coloring for cellular channel allocation", Discrete Applied Math. 182, 46-60, 2015.
  • [Bal09] N. Bartolini, T. Calamoneri, T. La Porta, A. Massini, S. Silvestri, " Autonomous deployment of heterogeneous mobile sensors ", Proc. of 17th IEEE Int.l Conference on Networks Protocols (ICNP '09)
  • [CP04] T. Calamoneri, R. Petreschi, "L(h,1)-Labeling Subclasses of Planar Graphs", Journal on Parallel and Distributed Computing, 64(3), pp. 414-426, 2004.
  • [Cal15] Gui Citovsky, Jie GaoJoseph S. B. MitchellJiemin Zeng. "Exact and Approximation Algorithms for Data Mule Scheduling in a Sensor Network", International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), pp. 57-70, 2015.
  • [Cal01] A. Clementi, P. Crescenzi, P. Penna, G. Rossi and P. Vocca. On the Complexity of Computing Minimum Energy Consumption Broadcast Subgraphs. 18th STACS'01, LNCS 2010, 2001.
  • [EE00] G. Even, S. Even: Embedding Interconnection Networks in Grids via the Layered Cross Product, Networks 36(2), pp. 91-95, 2000.
  • [GY92] J.R. Griggs, R.K. Yeh: Labelling graphs with a condition at distance 2. SIAM J. Disc. Math. 5(4), 586-595, 1992.
  • [Mal99] N. McKeown, A. Mekkittikul, V. Anantharam, J. Walrand: Achieving 100% throughput in an input queued switch. IEEE Trans. on Communications, 47(8), 1999.
  • [Mal17] P.L.A.Munhoz, U. dos Santos Souza, P.H.Gonzalez, L. Satoru Ochi, P. Michelon, L.M.de A. Drummond. "Locality sensitive heuristics for solving the Data Mule Routing Problem", 2017
  • [SG07] Ryo Sugihara, Rajesh K. Gupta: Data Mule Scheduling in Sensor Networks:Scheduling under Location and Time Constraints. UCSD CSE Technical Report CS2007-0911.
  • [WCLF02] P.-J. Wan, G. Calinescu, X.-Y. Li, O. Frieder. Minimum-Energy Broadcast Routing in Static ad-hoc Wireless Networks. Wireless Networks 8(6), 607 8211; 617, 2002.
  • [W81] D.S. Wise: Compact Layouts of Banyan/FFT Networks, VLSI Systems and Computations, pp.186-195, 1981.
  • [YP97] C.-H. Yeh, B. Parhami: VLSI Layouts of Complete graphs and star graphs. Information Processing Letters 68, pp. 39-45, 1998.
  • [YVP99] C.-H. Yeh, E.A. Varvarigos, and B. Parhami: Efficient VLSI layouts of hypercubic networks, Proc. Symp. Frontiers of Massively Parallel Computation, 1999, pp. 98- 105

Articoli per tesine/Papers for lessons

  • [Aal14] A.Antoniadis, N.Barcelo, D.Cole, K.Fox, B.Moseley, M.Nugent, K.Pruhs, Packet Forwarding Algorithms in a Line Network, Proc. LATIN 2014, LNCS 8392, pp. 610–621, 2014.
  • [AGK08] E. Aryafar, O. Gurewitz, E.W. Knightly, Distance-1 Constrained Channel Assignment in Single Radio Wireless Mesh Networks, IEEE INFOCOM 2008.
  • [BPT00] A. Bertossi, C. Pinotti, R.B. Tan. Efficient use of radio spectrum in wireless networks with Channel Separation between Close Stations. Dial M 2000.
  • [BKTL04] H. L. Bodlaender, T. Kloks, R. B. Tan, J. van Leeuwen: Approximations for lambda-Colorings of Graphs. Comput. J. 47(2): 193-204 (2004)
  • [Bal07] H. Broersma, F. Fomin, P. Golovach, G. Woeginger, "Backbone coloring for graphs: tree and path backbones", J. of Graph Theory 55(2), 2007.
  • [CM06] T. Calamoneri, A. Massini, "Nearly Optimal Three Dimensional Layout of Hypercube Networks", Networks , 47(19), pp. 1-8, 2006.
  • [Cal05] J. Cartigny, F. Ingelrest, D. Simplot-Ryl, I. Stojmenovic, Localized LMST and RNG based minimum-energy broadcast protocols in ad hoc networks, Ad Hoc Networks 3 (2005) 1–16
  • [Cal14] B.Caskurlu, V.Mkrtchyan, O.Parekh, K. Subramani, On Partial Vertex Cover and Budgeted Maximum Coverage Problems in Bipartite Graphs, Proc. of TCS 2014, LNCS 8705, pp. 13–26, 2014
  • [CL03] G. J. Chang and S.-C. Liaw, The L(2, 1)-labeling problem on ditrees, Ars Combin. 66 (2003), 23-31
  • [CB05] Y.CHAN, S.F.BAKER.The Multiple Depot, Multiple Traveling Salesmen Facility-Location Problem: Vehicle Range, Service Frequency, and Heuristic Implementations. Mathematical and Computer Modelling 41 (2005) 1035-1053.
  • [Dal99] Y. Dinitz, S. Even, R. Kupershtok, M. Zapolotsky. Some Compact Layouts of the Butterfly. SPAA 99.
  • [FNP06] Flammini, Navarra, Perennes, The real approximation factor of the MST heuristic for the minimum energy broadcasting, Journal of Experimental Algorithmics (JEA) 11, 2006
  • [Gal11] L.Giarré, F.G.La Rosa, R.Pesenti, I.Tinnirello, Coloring-based Resource Allocations in Ad-hoc Wireless Networks, Proc. 10th IFIP Annual Mediterranean Ad Hoc Networking Workshop, 2011
  • [GDW12] N.Goddemeier, K.Daniel,C.Wietfeld. Role-Based Connectivity Management with Realistic Air-to-Ground Channels for Cooperative UAVs. IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 30(5), 2012.
  • [GG01] R. Greenberg, L. Guan. On the Area of Hypercube Layouts. Arxiv:cs/0105034. Inf. Process. Lett. 84(1): 41-46 (2002)
  • [HZ14] Zi-Qi Hao, Zhen-Jiang Zhang. "Two Centralized Energy-Efficient Deployment Algorithms for Mobile Nodes in a Mixed Wireless Sensor Network" Journal of Computers. 2014.
  • [HV05] N. Heo and P. K. Varshney, Energy-Efficient Deployment of Intelligent Mobile Sensor Networks, IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS 8212;PART A: SYSTEMS AND HUMANS, 35(1), 2005
  • [Kal14] I.Khoufi, P.Minet, A.Laouiti, S.Mahfoudh. "Survey of Deployment Algorithms in Wireless Sensor Networks: Coverage and Connectivity Issues and Challenges"International Journal of Autonomous and Adaptive Communications Systems (IJAACS), 2014
  • [L94] D. Lischinski. Incremental Delaunay Triangulation. In Graphics Gems IV, Paul. S. Heckbert, editor, Academic Press, 1994.
  • [M95] T. Matsui. The minimum spanning tree problem on a planar graph. Discr. Appl. Math. 58 91-94, 1995.
  • [M11] H. Morizumi. Improved approximation algorithms for minimum AND-circuits problem via k-set cover. Information Processing Letters 111 218-221, 2011.
  • [NSM16] E. Niewiadomska-Szynkiewicz, A. Sikora, M. Marks. "A Movement-Assisted Deployment of Collaborating Autonomous Sensors for Indoor and Outdoor Environment Monitoring" Sensors, 2016.
  • [SS12] R.Saket, M.Sviridenko. "New and Improved Bounds for the Minimum Set Cover Problem" APPROX 2012.
  • [TJK08] G.Tan, S.A.Jarvis, A.M.Kermarrec. "Connectivity-Guaranteed and Obstacle-Adaptive Deployment Schemes for Mobile Sensor Networks" ICDCS 2008.
  • [TV05] L. Torok, Imrich Vrto. Layout volumes of the hypercubes. Proc. GD 04. LNCS 2005.
  • [YWD06] S.Yang, J.Wu, F.Dai. "Localized Movement-Assisted Sensor Deployment in Wireless Sensor Networks", MASS 2006.
  • [W14] S.Wan, Energy-Efficient and Adaptive Algorithms for Constructing Multipath Routing in Wireless Sensor Networks, Proc. NPC 2014, LNCS 8707, pp. 383–394, 2014.
  • [WCL06] G. Wang, G. Cao, and T. La Porta. Movement-assisted sensor deployment, IEEE Trans. on Mobile Computing, vol. 6, pp. 640-652, 2006.
  • [Xal14] J.Xu, W.Li, Z. Ma, S.Zhang, A New Channel Allocation Scheme for Vehicle Communication Networks, Proc. WASA 2014, LNCS 8491, pp. 66–77, 2014.
  • [YP01] Yeh, Parhami. On the VLSI Area and Bisection Width of Star Graphs and Hierarchical Cubic Networks. IPDPS 2001 pp. 72-79, 2001.

Edit | Attach | Watch | Print version | History: r46 < r45 < r44 < r43 < r42 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r46 - 2018-10-03 - TizianaCalamoneri





 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2018 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback