Том 18, номер 6, 2011 г., Стр. 17-32
УДК 519.8
Ерзин А. И., Плотников Р. В.
О максимизации времени функционирования сенсорных сетей при ресурсных ограничениях
Аннотация:
Рассматривается задача максимизации времени жизни сенсорной сети в условиях ограниченности ресурсов сенсоров в виде задачи целочисленного линейного программирования, в которой при заданном множестве покрытий требуется определить время функционирования каждого покрытия. При этом ресурс сенсора задаётся количеством временных раундов, в течение которых он может находиться в активном состоянии. Доказана NP-трудность задачи в сильном смысле. Предложены способы её упрощения. Показано, что для любого$\varepsilon>0$ задача в общем случае не аппроксимируема полиномиальными алгоритмами с точностью$O(m^{1-\varepsilon})$ , где$m$ – число покрытий. Найдены частные случаи, когда задача полиномиально разрешима. Предложено несколько эвристических алгоритмов построения приближённого решения задачи и проведён апостериорный анализ.
Табл. 1, библиогр. 18.
Ключевые слова: сенсорная сеть, максимизация времени жизни, расход энергии, целочисленное линейное программирование.
Ерзин Адиль Ильясович 1,2
Плотников Роман Викторович 2
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: adilerzin@math.nsc.ru, nomad87@ngs.ru
Статья поступила 12 апреля 2011 г.
Исправленный вариант — 16 июня 2011 г.
Литература
[1] Астраков С. Н., Ерзин А. И., Залюбовский В. В. Сенсорные сети и покрытие плоскости кругами // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 3. — С. 3–19.
[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. — М.: Мир, 1982. — 416 c.
[3] Харари Ф. Теория графов. — М.: Мир, 1973. — 296 c.
[4] Berman P., Fujito T. Approximating independent sets in degree 3 graphs // Proc. 4th Workshop Algorithms Data Structures. — Berlin: Springer-Verl., 1995. — P. 449–460. (Lect. Notes Comput. Sci.; Vol. 955.)
[5] Berman P., Calinescu G., Shan C., Zelikovsky A. Power efficient monitoring management in sensor networks // Proc. IEEE Wireless Communications Networking Conf. (Atlanta, USA, March 21–25, 2004). — Los Alamitos, CA: IEEE Comp. Soc., 2006. — P. 2329–2334.
[6] Berman P. Karpinski M. On some tighter inapproximability results // Tech. Rep. TR98–065, ECCC, 1998.
[7] Cardei M., Ding-Zhu D. Improving wireless sensor network lifetime through power aware organization // Springer Sci., Business Media, Wireless Networks 11, Netherlands, 2005 — P. 333–340.
[8] Cardei M., Thai M. T., Li Y., WuW. Energy-efficient target coverage in wireless sensor networks // IEEE Infocom. — 2005. — Vol. 3. — P. 1976–1984.
[9] Dhawan A., Vu C. T., Zelikovsky A., Li Y., Prasad S. K. Maximum life-time of sensor networks with adjustable sensing range // Proc. 7th ACIS Int. Conf. Software Engineering (Las Vegas, Nevada, USA, June 19–20, 2006). — Los Alamitos: IEEE Comp. Soc., 2006. — P. 285–289.
[10] Garg N., Konemann J. Faster and simpler algorithms for multicommodity flow and other fractional packing problems // Proc. FOCS (Palo Alto, CA, USA, November 8–10, 1998). —Washington: IEEE Comp. Soc., 1998. — P. 300–309.
[11] Gavril F. Algorithms on circular-arc graphs // Networks. — 1974. — Vol. 4. — P. 357–369.
[12] Ghouila-Houri A. Caractérisation des matrices totalement unimodulaires // CR hebdomadaires des séances de l’Académie des sciences, Paris, 1962. — P. 1192–1194.
[13] Håstad G. Clique is hard to approximate within $n^{1 - \epsilon}$ // Tech. Rep. TR97–038, ECCC, 1997.
[14] Hopcroft J., Karp R. An $n^{5/2}$ algorithm for maximum matchings in bipartite graphs // SIAM J. Comput. — 1973. — Vol. 2. — P. 225—231.
[15] Inanc M., Magdon-Ismail M., Yener B. Power optimal connectivity and coverage in wireless sensor networks // Department of Computer Science, Rensselaer Polytechnic Institute. — Troy, NY: Rensselaer Polytech. Inst. Publ., 2003.
[16] Kim Y., Lee H., Han Y. Jeonge Y. A branch and bound algorithm for extending the lifetime of wireless sensor networks // Proc. Vehicular Tech. Conf. (Anchorage, AK, September 20–23, 2009). — Washington: IEEE Comp. Soc., 2009. — P. 1–5.
[17] Mucha M., Sankowski P. Maximum matchings via Gaussian elimination // Proc. 45th IEEE Symp. Foundations Comput. Sci. 2004 (Washington, DC, USA, October 17–19, 2004 ) . — Washington: IEEE Comp. Soc., 2004. — P. 248—255.
[18] Segal M. Improving lifetime of wireless sensor networks // Netw. Protocols Algorithms. — 2009. — Vol. 1, N 2. — P. 48–60.
