Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Truyền phát tiết kiệm năng lượng trong mạng không dây hoàn toàn
Tóm tắt
Trong các mạng không dây hoàn toàn, việc giảm thiểu tiêu thụ năng lượng là rất quan trọng vì trong hầu hết các trường hợp, các nút đều hoạt động bằng pin. Chúng tôi tập trung vào vấn đề phát sóng tối ưu về công suất, được biết là có thể khai thác tính chất phát sóng của truyền hình radio để tối ưu hóa tiêu thụ năng lượng. Vấn đề này dường như rất khó để giải quyết. Chúng tôi cung cấp một bằng chứng chính thức về độ phức tạp NP cho trường hợp tổng quát và đưa ra một kết quả độ phức tạp NP cho trường hợp hình học; trong trường hợp trước, cấu trúc mạng được biểu thị bằng một đồ thị tổng quát với trọng số tùy ý, trong khi ở trường hợp sau, khoảng cách Euclide được xem xét. Đối với trường hợp tổng quát, chúng tôi chỉ ra rằng không thể xấp xỉ tốt hơn O(log N), trong đó N là tổng số nút. Sau đó, chúng tôi mô tả một thuật toán xấp xỉ đạt được tỷ lệ xấp xỉ O(log N). Chúng tôi cũng mô tả một heuristics mới, Lợi thế Đa phát không dây nhúng. Chúng tôi chỉ ra rằng nó so sánh tốt với các đề xuất khác và giải thích cách mà nó có thể được phân phối.
Từ khóa
#truyền phát #mạng không dây #tiết kiệm năng lượng #độ phức tạp NP #thuật toán xấp xỉTài liệu tham khảo
M. Čagalj, J.-P. Hubaux and C. Enz, Minimum-energy broadcast in all-wireless networks: NP-completeness and distribution issues, in: Proceedings of the 8th Annual International Conference on Mobile Computing and Networks (MOBICOM 2002), Atlanta, GA (September 2002) pp. 172–182.
J. Chang and L. Tassiulas, Energy conserving routing in wireless ad-hoc networks, in: Proceedings of IEEE INFOCOM 2000 (ACM, 2000) pp. 22–31.
A. Clementi, P. Crescenzi, P. Penna, G. Rossi and P. Vocca, On the complexity of computing minimum energy consumption broadcast subgraphs, in: Proceedings of 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2001) (2001) pp. 121–131.
T. Cormen, C. Leiserson, R. Rivest and C. Stein, Introduction to Algorithms, 2nd ed. (MIT Press, 2001).
O. Eğecioğlu and T. Gonzalez, Minimum-energy broadcast in simple graphs with limited node power, in: Proceedings of IASTED International Conference on Parallel and Distributed Computing and Systems (PDCS 2001), Anaheim, CA (August 2001) pp. 334–338.
D. Estrin, R. Govindan, J. Heidemann and S. Kumar, Next century challenges: scalable coordination in sensor networks, in: Proceedings of the 5th Annual International Conference on Mobile Computing and Networks (MOBICOM 1999), Seattle, WA (August 1999) pp. 271–278.
A. Faragó and V. Syrotiuk, Algorithmic problems in power controlled ad hoc networks, in: Proceedings of the 14th International Conference on Parallel and Distributed Computing Systems (PDCS 2001), Dalas, TX (August 2001).
R. Gallager, P. Humblet and P. Spira, A distributed algorithm for minimum-weight spanning trees, ACM Transactions on Programming Languages and Systems 5(1) (1983) 66–77.
M. Garey and D. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).
W. Heinzelman, A. Chandrakasan and H. Balakrishnan, Energy-efficient communication protocol for wireless microsensor networks, in: Proceedings of the 33rd Hawaii International Conference on System Sciences (HICSS 2000), Maui, HI (January 2000).
D.S. Hochbaum, Approximation Algorithms for NP-Hard Problems (PWS, 1997).
J.-P. Hubaux, T. Gross, J.-Y.L. Boudec and M. Vetterli, Towards self-organized mobile ad hoc networks: the Terminodes Project, IEEE Communications Magazine 39(1) (2001) 118–124.
E.-S. Jung and N. Vaidya, An energy efficient MAC protocol for wireless LANs, in: IEEE INFOCOM 2002, New York, USA (June 2002) pp. 1756–1764.
F. Li and I. Nikolaidis, On minimum-energy broadcasting in all-wireless networks, in: Proceedings of the 26th Annual IEEE Conference on Local Computer Networks (LCN 2001), Tampa, FL (November 2001) pp. 143–202.
Q. Li, J. Aslam and D. Rus, Online power-aware routing in wireless ad-hoc networks, in: Proceedings of the 7th Annual International Conference on Mobile Computing and Networks (MOBICOM 2001), Rome, Italy (July 2001) pp. 97–107.
W. Liang, Constructing minimum-energy broadcast trees in wireless ad hoc networks, in: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC 2002), Lausanne, Switzerland (June 2002).
D. Lichtenstein, Planar formulae and their uses, SIAM Journal on Computing 11(2) (1982) 329–343.
K. Makki, N. Pissinou and O. Frieder, Efficient solutions to multicast routing in communication networks, Mobile Networks and Applications 1(2) (1996) 221–232.
M. Nagy and S. Singh, Multicast scheduling algorithms in mobile networks, Cluster Computing 1(2) (1998) 177–185.
G. Pottie and W. Kaiser, Wireless integrated network sensors, Communication of the ACM 43(5) (May 2000) 51–58.
J. Rabaey, M. Ammer, J. da Silva Jr., D. Patel and S. Roundy, PicoRadio supports ad hoc ultra-low power wireless networking, IEEE Computer Magazine 33(7) (2000) 42–48.
T.S. Rappaport, Wireless Communications: Principles and Practice (Prentice Hall, 1996).
V. Rodoplu and T.H. Meng, Minimum energy mobile wireless networks, IEEE Journal on Selected Areas in Communications 17(8) (1999) 1333–1344.
C. Schurgers, V. Tsiatsis, S. Ganeriwal and M.B. Srivastava, Optimizing sensor networks in the energy-latency-density design space, IEEE Transactions on Mobile Computing 1(1) (2002) 70–80.
S. Singh, C. Raghavendra and J. Stepanek, Power-aware broadcasting in mobile ad hoc networks, in: Proceedings of IEEE PIMRC’99, Osaka, Japan (September 1999) pp. 22–31.
V.V. Vazirani, Approximation Algorithms (Springer, 2001).
B.K.J. Vygen, Combinatorial Optimization. Theory and Algorithms (Springer, 2000).
P.-J. Wan, G. Calinescu and O.F.X.-Y. Li, Minimum-energy broadcast routing in static ad hoc wireless networks, in: IEEE INFOCOM 2001, Anchorage, AL (April 2001) pp. 1162–1171.
R. Wattenhofer, L. Li, V. Bahl and Y. Wang, Distributed topology control for power efficient operation in multihop wireless ad hoc networks, in: Proceedings of IEEE INFOCOM 2001 (April 2001) pp. 1388–1397.
J.E. Wieselthier, G.D. Nguyen and A. Ephremides, On the construction of energy-efficient broadcast and multicast trees in wireless networks, in: IEEE INFOCOM 2000, Tel Aviv, Israel (2000) pp. 586–594.
J.E. Wieselthier, G.D. Nguyen and A. Ephremides, Algorithms for energy-efficient multicasting in static ad hoc wireless networks, Mobile Networks and Applications 6(3) (2001) 251–263.
Y. Xu, J. Heidemann and D. Estrin, Geography-informed energy conservation for ad hoc routing, in: Proceedings of the 7th Annual International Conference on Mobile Computing and Networks (MOBICOM 2001) (July 2001) pp. 70–84.