Weitere Kapitel dieses Buchs durch Wischen aufrufen
Connectivity in wireless sensor networks may be established using either omnidirectional or directional antennae. The former radiate power uniformly in all directions while the latter emit greater power in a specified direction thus achieving increased transmission range and encountering reduced interference from unwanted sources. Regardless of the type of antenna being used the transmission cost of each antenna is proportional to the coverage area of the antenna. It is of interest to design efficient algorithms that minimize the overall transmission cost while at the same time maintaining network connectivity. Consider a set S of n points in the plane modeling sensors of an ad hoc network. Each sensor is equipped with a fixed number of directional antennae modeled as a circular sector with a given spread (or angle) and range (or radius). Construct a network with the sensors as the nodes and with directed edges (u,v) connecting sensors u and v if v lies within u’s sector. We survey recent algorithms and study trade-offs on the maximum angle, sum of angles, maximum range, and the number of antennae per sensor for the problem of establishing strongly connected networks of sensors.
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
L. Bao and J. J. Garcia-Luna-Aceves. Transmission scheduling in ad hoc networks with directional antennas. Proceedings of the 8th Annual International Conference on Mobile Computing and Networking, pages 48–58, Atlanta, Georgia, USA, 2002.
B. Bhattacharya, Y Hu, E. Kranakis, D. Krizanc, and Q. Shi. Sensor Network Connectivity with Multiple Directional Antennae of a Given Angular Sum. 23rd IEEE International Parallel and Distributed Processing Symposium (IPDPS 2009), May 25–29, Rome, Italy, 2009.
I. Caragiannis, C. Kaklamanis, E. Kranakis, D. Krizanc, and A. Wiese. Communication in Wireless Networks with Directional Antennae. In proceedings of 20th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA’08), June 14–16, pages 344–351, Munich, Germany, 2008.
E. Chávez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho, and J. Urrutia. Local Construction of Planar Spanners in Unit Disk Graphs with Irregular Transmission Ranges. In LATIN 2006, LNCS, Vol. 3887, pages 286–297, 2006.
J. Cheriyan, A. Sebö, and Z. Szigeti. An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs. In Proceedings of the 6th International IPCO Conference on Integer Programming and Combinatorial Optimization, Vol. 1412, pages 126–136. Springer, Berlin, 1998.
J. Czyzowicz, S. Dobrev, H. Gonzalez-Aguilar, R. Kralovic, E. Kranakis, J. Opatrny, L. Stacho, and J. Urrutia. Local 7-Coloring for Planar Subgraphs of Unit Disk Graphs. In Theory and Applications of Models of Computation: 5th International Conference, TAMC 2008, Xi’an, China, April 25-29, 2008; Proceedings, vol. 4978, pages 170–181. Springer, Berlin, 2008.
S. Dobrev, E. Kranakis, D. Krizanc, O. Morales, J. Opatrny, and L. Stacho. Strong connectivity in sensor networks with given number of directional antennae of bounded angle, 2010. COCOA 2010, to appear.
Q. Dong and Y. Bejerano. Building Robust Nomadic Wireless Mesh Networks Using Directional Antennas. In IEEE INFOCOM 2008. The 27th Conference on Computer Communications, pages 1624–1632, Phoenix, AZ, USA, 2008.
A. Francke and M. Hoffmann. The Euclidean degree-4 minimum spanning tree problem is NP-hard. In Proceedings of the 25th Annual Symposium on Computational Geometry, pages 179–188. ACM, New York, NY, 2009.
T. Fukunaga. Graph Orientations with Set Connectivity Requirements. In Proceedings of the 20th International Symposium on Algorithms and Computation, pages 265–274. Springer, LNCS, Honolulu, Hawaii, 2009.
L. Hu and D. Evans. Using directional antennas to prevent wormhole attacks. In Network and Distributed System Security Symposium (NDSS), pages 131–141. Internet Society, San Diego, California, USA, 2004.
H. Imai, K. Kobara, and K. Morozov. On the possibility of key agreement using variable directional antenna. In Proc. of 1st Joint Workshop on Information Security,(Korea). IEICE, 2006.
T. R. Jensen and B. Toft. Graph Coloring Problems. Wiley-Interscience, New York, NY, 1996.
S. Khuller, B. Raghavachari, and N. Young. Low degree spanning trees of small weight. In Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, page 421. ACM, Montreal, Quebec, Canada, 1994.
E. Kranakis, D. Krizanc, and J. Urrutia. Coverage and Connectivity in Networks with Directional Sensors. proceedings Euro-Par Conference, Pisa, Italy, August, pages 917–924, Pisa, Italy, 2004.
E. Kranakis, D. Krizanc, and E. Williams. Directional versus omnidirectional antennas for energy consumption and k-connectivity of networks of sensors. Proceedings of OPODIS, 3544:357–368, 2004.
E. Kranakis, O. Morales, and L. Stacho. On orienting planar sensor networks with bounded stretch factor, 2010. Unpublished manuscript.
X. Li, G. Calinescu, P Wan, and Y. Wang. Localized Delaunay Triangulation with Application in Ad Hoc Wireless Networks. IEEE Transactions on Parallel and Distributed Systems, 14:2003, 2003.
X. Lu, F. Wicker, P. Lio, and D. Towsley. Security Estimation Model with Directional Antennas. In IEEE Military Communications Conference, 2008. MILCOM 2008, pages 1–6, 2008.
V. Navda, A. P. Subramanian, K. Dhanasekaran, A. Timm-Giel, and S. Das. Mobisteer: using steerable beam directional antenna for vehicular network access. In ACM MobiSys, 2007.
R. Ramanathan. On the performance of ad hoc networks with beamforming antennas. Proceedings of the 2nd ACM International Symposium on Mobile Ad Hoc Networking & Computing, pages 95–105, Long Beach, CA, USA, 2001.
A. Spyropoulos and C. S. Raghavendra. Energy efficient communications in ad hoc networks using directional antennas. INFOCOM 2002: Twenty-First Annual Joint Conference of the IEEE Computer and Communications Societies, New York, NY, USA, 2002.
A. Spyropoulos and C. S. Raghavendra. Capacity bounds for ad-hoc networks using directional antennas. ICC’03: IEEE International Conference on Communications, Anchorage, Alaska, USA, 2003.
S. Yi, Y. Pei, and S. Kalyanaraman. On the capacity improvement of ad hoc wireless networks using directional antennas. Proceedings of the 4th ACM International Symposium on Mobile Ad Hoc Networking & Computing, pages 108–116, Annapolis, Maryland, USA, 2003.
- Maintaining Connectivity in Sensor Networks Using Directional Antennae
- Springer Berlin Heidelberg
- Chapter 3