Efficient broadcasting in multi-hop wireless networks with a realistic physical layer
Authors: Gary K.W. Wong, Hai Liu, Xiaowen Chu, Yiu-Wing Leung, Chun Xie
Abstract:
Almost all existing broadcasting algorithms assume an ideal physical layer, in which a successful transmission is guaranteed if the distance between communicating nodes is less than a certain threshold, e.g., a transmission range. However, wireless communication links normally suffer from the characteristics of realistic physical layer, which significantly reduce the reliability of broadcasting among the nodes. This work addresses the minimal broadcasting problem in multi-hop wireless networks with a realistic physical layer. Given a probability p , the problem is to design a distributed broadcasting algorithm such that each node in the network receives the broadcasting packet with probability no less than p and the number of retransmissions is minimized. We show that this problem is NP-hard and propose a distributed greedy algorithm which maximizes the gain cost ratio at each node. We prove that the proposed algorithm guarantees that each node receives the broadcasting packet with probability no less than p , and analyze upper bound on the number of total retransmissions in the network. Simulation results show that our algorithm can provide near 100% coverage to the wireless network with a realistic physical layer, and reduce the number of retransmissions compared with modified traditional flooding schemes kFlooding (pure flooding with multiple times) and ACK-Flooding (pure flooding with acknowledgement). We believe our algorithmic solution is efficient and practical for general existing multi-hop wireless networks.
Keywords:
Energy-efficiency wireless
Multi-hop wireless network
Broadcasting efficiency
Unreliable network
NP-hardness
Minimum retransmission broadcast problem
Published in: Ad Hoc Networks (Volume 11, Issue 4, January 2013)
Publisher: Elsevier
ISSN Information: 1570-8705
Efficient broadcasting in multi-hop wireless networks with a realistic physical layer
- Vòng Sơ Khảo Cuộc Thi Đại Sứ Văn Hóa Đọc Năm 2024
- Ngày hội sách “CITTADELLA” khuyến khích và tôn vinh vai trò của sách trong sinh viên Bách khoa
- Cuộc Thi Ảnh “Khoảnh Khắc VNUHCM Libraries”
- Ngày hội Văn hóa đọc lần VI
- Ngày hội văn hóa đọc lần V
- Ngày hội văn hóa đọc lần II
- Ngày hội văn hóa đọc lần IV
- Ngày hội văn hóa đọc lần III
- Tiếp GS Omer Mert Denizci, Trường ĐH Marmara Thổ Nhĩ Kỳ
- Tiếp Cô Claudia Tarzariol Từ The University Of Trento, Italy (Unitrento)
- Tiến sĩ kiều bào Mỹ tặng sách trị giá 150.000 USD cho sinh viên bách khoa
- Khảo sát ý kiến bạn đọc
-
Trực tuyến:18
-
Hôm nay:6653
-
Tuần này:6653
-
Tuần trước:35140
-
Tháng trước:35140
-
Tất cả:4116520