On the Placement of Internet Taps in Wireless Neighborhood Networks
Lili Qiu, Ranveer Chandra, Kamal Kishore Jain, Mohammad Mahdian · 2003
Recently there has emerged a novel application of wireless technology that enables home users to connect to the Internet by creating a multi-hop wireless network over a neighborhood region. In such a network, a small number of Internet TAPs (ITAPs) are deployed across the neighborhood, serving as gateways to the Internet; houses are equipped with low-cost antennas, and form a multi-hop wireless network among themselves to cooperatively route traffic to the Internet using the ITAPs. A similar application also exists in sensor networks, where sensors collect measurement data and send it through a multi-hop wireless network to the servers on the Internet via ITAPs. For both applications, placement of ITAPs is a critical determinant of system performance and resource usage. However there has been little work on this subject. In this paper, we explore the ITAP placement problem under three wireless link models. For each link model, we develop placement algorithms to make informed placement decisions based on neighborhood layouts, user demands, and wireless link characteristics. We also extend our algorithms to provide fault tolerance and to handle significant workload variation. We evaluate our placement algorithms through both analysis and simulation. Our results show that our algorithms yield close to optimal solutions over a wide range of scenarios we have considered.