Competitive throughput in multi-hop wireless networks despite adaptive jamming
Tóm tắt
This article presents a simple local medium access control protocol, called Jade, for multi-hop wireless networks with a single channel that is provably robust against adaptive adversarial jamming. The wireless network is modeled as a unit disk graph on a set of nodes distributed arbitrarily in the plane. In addition to these nodes, there are adversarial jammers that know the protocol and its entire history and that are allowed to jam the wireless channel at any node for an arbitrary $$(1-\epsilon )$$ -fraction of the time steps, where $$0<\epsilon <1$$ is an arbitrary constant. We assume that nodes can perform collision detection (unless they are transmitting themselves), but that they cannot distinguish between jammed transmissions and collisions of regular messages. Nevertheless, we show that Jade achieves an asymptotically optimal throughput by efficiently exploiting the unpredictable time periods in which the medium is available.
Tài liệu tham khảo
Alnifie, G., Simon, R.: A multi-channel defense against jamming attacks in wireless sensor networks. In: Proceedings of Q2SWinet ’07, pp. 95–104 (2007)
Awerbuch, B., Richa, A., Scheideler, C.: A jamming-resistant MAC protocol for single-hop wireless networks. In: Proceedings of PODC ’08 (2008)
Bayraktaroglu, E., King, C., Liu, X., Noubir, G., Rajaraman, R., Thapa, B.: On the performance of IEEE 802.11 under jamming. In: Proceedings of IEEE Infocom ’08, pp. 1265–1273 (2008)
Bender, M.A., Farach-Colton, M., He, S., Kuszmaul, B.C., Leiserson, C.E.: Adversarial contention resolution for simple channels. In: Proceedings of SPAA ’05 (2005)
Brown, T., James, J., Sethi, A.: Jamming and sensing of encrypted wireless ad hoc networks. In: Proceedings of MobiHoc ’06, pp. 120–130 (2006)
Chiang, J., Hu, Y.-C.: Cross-layer jamming detection and mitigation in wireless broadcast networks. In: Proceedings of MobiCom ’07, pp. 346–349 (2007)
Chlebus, B.S., Kowalski, D.R., Rokicki, M.A.: Adversarial queuing on the multiple-access channel. In: Proceedings of PODC ’06 (2006)
citation_journal_title=J. Algorithms; citation_title=Broadcasting algorithms in radio networks with unknown topology; citation_author=A Czumaj, W Rytter; citation_volume=60; citation_issue=2; citation_publication_date=2006; citation_pages=115-143; citation_doi=10.1016/j.jalgor.2004.08.001; citation_id=CR8
Dolev, S., Gilbert, S., Guerraoui, R., Kowalski, D., Newport, C., Kuhn, F., Lynch, N.: Reliable distributed computing on unreliable radio channels. In: Proceedings of the 2009 MobiHoc S3 Workshop (2009)
Dolev, S., Gilbert, S., Guerraoui, R., Kuhn, F., Newport, C.C.: The wireless synchronization problem. In: Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing (PODC), pp. 190–199 (2009)
Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.: Gossiping in a multi-channel radio network: An oblivious approach to coping with malicious interference. In: Proceedings of the Symposium on Distributed Computing (DISC) (2007)
Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.: Secure communication over radio channels. In: Proceedings of the 27th ACM Symposium on Principles of Distributed Computing (PODC), pp. 105–114 (2008)
Dolev, S., Gilbert, S., Guerraoui, R., Newport, C.C.: Gossiping in a multi-channel radio network. In: Proceedings of the 21st International Symposium on Distributed Computing (DISC), pp. 208–222 (2007)
Gilbert, S., Guerraoui, R., Kowalski, D., Newport, C.: Interference-resilient information exchange. In: Proceedings of the 28th Conference on Computer Communications. IEEE Infocom 2009 (2009)
Gilbert, S., Guerraoui, R., Kowalski, D.R., Newport, C.C.: Interference-resilient information exchange. In: Proceedings of the 28th IEEE International Conference on Computer Communications (INFOCOM), pp. 2249–2257 (2009)
Gilbert, S., Guerraoui, R., Newport, C.: Of malicious motes and suspicious sensors: On the efficiency of malicious interference in wireless networks. In: Proceedings of OPODIS ’06 (2006)
citation_journal_title=J. ACM; citation_title=Contention resolution with constant expected delay; citation_author=L.A. Goldberg, P.D. Mackenzie, M. Paterson, A. Srinivasan; citation_volume=47; citation_issue=6; citation_publication_date=2000; citation_pages=1048-1096; citation_id=CR17
Håstad, J., Leighton, T., Rogoff, B.: Analysis of backoff protocols for mulitiple access channels. SIAM J. Comput. 25(4) 710–774 (1996).
http://dx.doi.org/10.1137/S0097539792233828
Heusse, M., Rousseau, F., Guillier, R., Duda, A.: Idle sense: An optimal access method for high throughput and fairness in rate diverse wireless lans. In: Proceedings of SIGCOMM (2005)
IEEE: Medium access control (MAC) and physical specifications. In: IEEE P802.11/D10 (1999)
Jain, K., Padhye, J., Padmanabhan, V.N., Qiu, L.: Impact of interference on multi-hop wireless network performance. In: Proceedings of the 9th Annual International Conference on Mobile Computing and Networking (MobiCom), pp. 66–80 (2003)
Jiang, S., Xue, Y.: Providing survivability against jamming attack via joint dynamic routing and channel assigment. In: Proceedings of the 7th Workshop on Design of Reliable Communication Networks (DRCN) (2009)
Koo, C., Bhandari, V., Katz, J., Vaidya, N.: Reliable broadcast in radio networks: The bounded collision case. In: Proceedings of PODC ’06 (2006)
Kuhn, F., Moscibroda, T., Wattenhofer, R. Radio network clustering from scratch. In: Proceedings. of ESA ’04 (2004)
citation_journal_title=IEEE/ACM Trans. Netw.; citation_title=Performance analysis of exponential backoff; citation_author=B-J Kwak, N-O Song, LE Miller; citation_volume=13; citation_issue=2; citation_publication_date=2005; citation_pages=343-355; citation_doi=10.1109/TNET.2005.845533; citation_id=CR25
Law, Y., van Hoesel, L., Doumen, J., Hartel, P., Havinga, P.: Energy-efficient link-layer jamming attacks against wireless sensor network mac protocols. In: Proceedings of SASN ’05, pp. 76–88 (2005)
Li, M., Koutsopoulos, I., Poovendran, R.: Optimal jamming attacks and network defense policies in wireless sensor networks. In: Proceedings of Infocom ’07, pp. 1307–1315 (2007)
Liu, X., Noubir, G., Sundaram, R., Tan, S.: Spread: Foiling smart jammers using multi-layer agility. In: Proceedings of Infocom ’07, pp. 2536–2540 (2007)
Meier, D., Pignolet Y.A., Schmid S., Wattenhofer, R.: Speed dating despite jammers. In: Proceedings of DCOSS ’09 June (2009)
Navda, V., Bohra, A., Ganguly, S., Rubenstein, D.: Using channel hopping to increase 802.11 resilience to jamming attacks. In: Proceedings of Infocom’07, pp. 2526–2530 (2007)
Negi, R., Perrig, A.: Jamming Analysis of MAC Protocols. Technical Report. Carnegie Mellon University (2003)
Noubir, G.: On connectivity in ad hoc networks under jamming using directional antennas and mobility. In: Proceedings of the 2nd International Conference on Wired/Wireless Internet Communications (WWIC), pp. 186–200 (2004)
Pelc A., Peleg, D.: Feasibility and complexity of broadcasting with random transmission failures. In: Proceedings of PODC ’05 (2005)
citation_journal_title=SIAM J. Comput.; citation_title=Stochastic contention resolution with short delays; citation_author=P Raghavan, E Upfal; citation_volume=28; citation_issue=2; citation_publication_date=1999; citation_pages=709-719; citation_doi=10.1137/S0097539795285333; citation_id=CR34
Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Competitive and fair medium access despite reactive jamming. In: Proceedings of the 31st International Conference on Distributed Computing Systems (ICDCS) (2011)
Richa, A., Scheideler, C., Schmid, S., Zhang, J.: Self-stabilizing leader election for single-hop wireless networks despite jamming. In: Proceedings of the 12th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc) (2011)
citation_journal_title=SIAM J. Discrete Math.; citation_title=Chernoff-Hoeffding bounds for applications with limited independence; citation_author=J Schmidt, A Siegel, A Srinivasan; citation_volume=8; citation_issue=2; citation_publication_date=1995; citation_pages=223-250; citation_doi=10.1137/S089548019223872X; citation_id=CR37
citation_title=Spread Spectrum Communications Handbook; citation_publication_date=2001; citation_id=CR38; citation_author=MK Simon; citation_author=JK Omura; citation_author=RA Schultz; citation_author=BK Levin; citation_publisher=McGraw-Hill
Thuente, D., Acharya, M. Intelligent jamming in wireless networks with applications to 802.11b and other networks. In: Proceedings of MILCOM ’06 (2006)
citation_journal_title=Perform. Eval.; citation_title=Achieving target throughputs in random-access networks; citation_author=PM Ven, AJEM Janssen, JSH Leeuwaarden, SC Borst; citation_volume=68; citation_publication_date=2011; citation_pages=1103-1117; citation_doi=10.1016/j.peva.2011.07.019; citation_id=CR40
Wood, A., Stankovic, J., Zhou, G. DEEJAM: Defeating energy-efficient jamming in IEEE 802.15.4-based wireless networks. In: Proceedings of SECON ’07 (2007)
citation_journal_title=IEEE Netw.; citation_title=Jamming sensor networks: attack and defense strategies; citation_author=W. Xu, K. Ma, W. Trappe, Y. Zhang; citation_volume=20; citation_issue=3; citation_publication_date=2006; citation_pages=41-47; citation_id=CR42
Xu, W., Trappe, W., Zhang, Y., Wood, T.: The feasibility of launching and detecting jamming attacks in wireless networks. In: Proceedings of MobiHoc ’05, pp. 46–57 (2005)
Xu, W., Wood, T., Zhang, Y.: Channel surfing and spatial retreats: defenses against wireless denial of service. In: Proceedings of Workshop on Wireless Security (2004)
Ye, S., Wang, Y., Tseng, Y. A jamming-based MAC protocol for wireless multihop ad hoc networks. In: Proceedings of the IEEE 58th Vehicular Technology Conference (2003)
citation_journal_title=Wirel. Commun. Mob. Comput.; citation_title=A jamming-based MAC protocol to improve the performance of wireless multihop ad-hoc networks; citation_author=S-R Ye, Y-C Wang, Y-C Tseng; citation_volume=4; citation_issue=1; citation_publication_date=2004; citation_pages=75-84; citation_doi=10.1002/wcm.170; citation_id=CR46
citation_journal_title=IEEE Trans. Netw.; citation_title=Jamming in slotted ALOHA multihop packed radio networks; citation_author=J Zander; citation_volume=39; citation_issue=10; citation_publication_date=1991; citation_pages=1525-1531; citation_id=CR47