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.

NOTE: Papers can be freely downloaded by connecting to the Sapienza network.


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:


2. wireless fixed 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:


3. fixed sensor networks

3.1. The data mule scheduling problem i.e. the traveling salesman problem

References:

Student lessons:

3.2. The data Collection in ad-hoc networks i.e. the connected Dominating Set Problem

References:

Student lessons:


4. mobile sensor networks

4.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:


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

References:

Student lessons:

For a thorough examination of the topic:

4.3. Monitoring by UAVs i.e. what?

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:


2. reti wireless fisse

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:


3. reti di sensori fisse 3.1. Il problema del data mule ovvero il problema del commesso viaggiatore

Riferimenti per studiare:

Tesine:

3.2. Il Data Collection in reti di sensori ovvero il problema dell'insieme dominante connesso

Riferimenti per studiare:

Tesine:


4. reti di sensori mobili

4.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:


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

Riferimenti per studiare:

Tesine:

Possibili approfondimenti:

4.3. Monitorare tramite UAVs ovvero TSP multiplo con vincoli (più o meno)

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 Algorithms, 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)
  • [CSS09] J. Chen, E. Shen, Y. Sun, "The Deployment Algorithms in Wireless Sensor Networks: a Survey", Information Technology Journal 8(3) 2009.
  • [Cal15] Gui Citovsky, Jie Gao Joseph S. B. Mitchell Jiemin 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.
  • [HMS02] A. Howard, M.J. Mataric, G.S. Sukhatme: Mobile Sensor Network Deployment using Potential Fields: A Distributed, Scalable Solution to the Area Coverage Problem. 6th International Symposium on Distributed Autonomous Robotics Systems (DARS02), 2002.
  • [L80] C.E. Leiserson: Area Efficient Graph Layouts (for VLSI). Proc. IEEE FOCS 1980.
  • [Mal99] N. Mc Keown, A. Mekkittikul, V. Anantharam, J. Walrand: Achieving 100% throughput in an input queued switch. IEEE Trans. on Communications, 47(8), 1999.
  • [PS10] G.N. Purohit and U. Sharma: Constructing Minimum Connected Dominating Set: Algorithmic approach. International journal on applications of graph theory in wireless ad hoc networks and sensor networks (GRAPH-HOC) Vol.2, No.3, September 2010
  • [Ral04] L. Ruana, H. Dub, X. Jiab, W. Wuc, Y. Lid, K. Ko. Agreedyapproximationforminimumconnected dominating sets. Theoretical Computer Science 329 (2004) 325 – 330.
  • [Sal19] W. Shi, W. Liu, T. Wang, Z. Zeng, G. Zhi: Adding Duty Cycle Only in Connected Dominating Sets for Energy Efficient and Fast Data Collection. IEEE Access, 7, 2019.
  • [SG07] R. Sugihara, R.K. Gupta: Data Mule Scheduling in Sensor Networks: Scheduling under Location and Time Constraints. UCSD CSE Technical Report CS2007-0911.
  • [WCL06] G. Wang, G. Cao, and T. La Porta. Movement-assisted sensor deployment, IEEE Trans. on Mobile Computing, vol. 6, pp. 640-652, 2006.
  • [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.
  • [WY06] J. Wu, S. Yang: Optimal Movement-Assisted Sensor Deployment and Its Extensions in Wireless Sensor Networks. Proceedings 12th International Conference on Parallel and Distributed Systems (ICPADS), 2006.
  • [YWD06] S.Yang, J.Wu, F.Dai. "Localized Movement-Assisted Sensor Deployment in Wireless Sensor Networks", MASS 2006.
  • [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.
  • [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.
  • [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.
  • [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
  • [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.
  • [Dal18] L.Deng, X.Ma, J.Gu, Y.Li "DETECTION AND REPAIR OF COVERAGE HOLES IN MOBILE SENSOR NETWORKS USING SUB-VORONOI CELLS" International Journal of Robotics and Automation - 2018
  • [Dal99] Y. Dinitz, S. Even, R. Kupershtok, M. Zapolotsky. Some Compact Layouts of the Butterfly. SPAA 99.
  • [Dal10] J.Du, Y.Li, H.Liu, K. Sha "On Sweep Coverage with Minimum Mobile Sensors", IEEE 16th International Conference on Parallel and Distributed Systems, pp. 283-290, 2010.
  • [Fal07] E. Filiol, E. Franc, A. Gubbioli, B. Moquet, G. Roblot: Combinatorial Optimisation of Worm Propagation on an Unknown Network. World Academy of Science, Engineering and Technology International Journal of Computer and Information Engineering Vol:1, No:10, 2007
  • [Fal10] G. Fletcher, X. Li, A. Nayak, I. Stojmenovic: Back-Tracking based Sensor Deployment by a Robot Team. Proceedings 7th IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks (SECON), 2010.
  • [FNP06] Flammini, Navarra, Perennes, The real approximation factor of the MST heuristic for the minimum energy broadcasting, Journal of Experimental Algorithmics (JEA) 11, 2006.
  • [Gal07] L. Gasieniec, E. Kantor, D.R. Kowalski, D. Peleg, C. Su, Energy and Time Efficient Broadcasting in Known Topology Radio Networks, Proc. DISC 2007, LNCS 4731, 2007.
  • [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.
  • [GR93] A.V.Goldberg, T.Radzik. A Heuristic Improvement of the Bellman-Ford Algorithm. Appl. Math. Lett. 6(3), 3-6 (1993).
  • [GM15] B. Gorain and P.S. Mandal "Energy Efficient Sweep Coverage with Mobile and Static Sensors", Proc. CALDAM 2015, LNCS 8959, pp. 275–285, 2015.
  • [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
  • [KM09] W. Klostermeyer, C.M.Mynhardt. "Edge protection in graphs", AUSTRALASIAN JOURNAL OF COMBINATORICS 45, 235-250, 2009.
  • [KM16] W. Klostermeyer, C.M.Mynhardt. "Protecting a Graph with Mobile Guards", Applicable Analysis and Discrete Mathematics 10, 2016.
  • [L80] C.E. Leiserson: Area Efficient Graph Layouts (for VLSI). Proc. IEEE FOCS 1980.
  • [LEV14] L. Levin, A. Efrat, M. Segal: Collecting data in ad-hoc networks with reduced uncertainty. Ad Hoc Networks 17, 71-81, 2014.
  • [LL23] I.-C. Liao, H.-I. Lu: A Simple 2-Approximation for Maximum Leaf Spanning Tree. IJFCS 34(7), 795-805, 2023.
  • [L94] D. Lischinski. Incremental Delaunay Triangulation. In Graphics Gems IV, Paul. S. Heckbert, editor, Academic Press, 1994.
  • [ML18] A.Majeed and S.Lee. "A Fast Global Flight Path Planning Algorithm Based on Space Circumscription and Sparse Visibility Graph for Unmanned Aerial Vehicle". Electronics 7(12)2018.
  • [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.
  • [Mal19] P.L.A. Munhoz, U. dos Santos Souza, P.H. Gonzales, L.S. Ochi, P. Michelon, L.M. de A. Drummond. "Locality sensitive heuristics for solving the Data Mule Routing Problem" ICAAM 2019.
  • [NCO13] M.NAKECHBANDI, J.-Y.COLIN, A.S.OULD CHEIKH. Routing and Rerouting in Weakly Dynamic Graphs. Proc. ECCS'13.
  • [NSM16] E. Niewiadomska-Szynkiewicz, A. Sikora, M. Marks. "A Movement-Assisted Deployment of Collaborating Autonomous Sensors for Indoor and Outdoor Environment Monitoring" Sensors, 2016.
  • [N08] A. Navarra. "3-Dimensional minimum energy broadcasting problem" Ad Hoc Networks 6, 734-743, 2008.
  • [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.
  • [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.
  • [WLC16] Y. Wu, C. Lu, Y. Chen "A survey of routing algorithm for mesh Network-on-Chip", Front. Comput. Sci., 10(4): 591–601, 2016.
  • [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.


This topic: Algoreti > WebHome1011 > ProgrammaDelCorso
Topic revision: r75 - 2023-12-21 - TizianaCalamoneri
 
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback