基於建立Wi-Fi連結最小化使用者移動距離之接取點配置

Access Point Placement for Minimizing User Moving Distance to Set Up a Wi-Fi Connection

鍾明儒(Ming-Ju Chung)

指導教授 ： 張時中

國立臺灣大學/電機資訊學院/電機工程學研究所/碩士(2012年)

https://doi.org/10.6342/NTU.2012.10344

摘要

Wi-Fi的出現解決了短距離無線通訊使用者對頻寬之需求，其網路層(含)以上相容於有線區域網路之特性也促使其易於設置且低成本之特性，目前已普遍應用於包含校園、辦公大樓、住宅…等區域。依不同的設計目標，設計者決定AP之配置位置、數量與使用頻道。經由實際觀察Wi-Fi使用者行為，本論文以使用者平均移動距離為最佳化之AP配置指標，考慮使用者需要移動才能接取Wi-Fi網路的情形下，找出使用者平均移動距離最短之AP配置。

研究首先探討AP配置相關議題。影響AP配置位置之因素有配置數量、不同Wi-Fi通訊協定(802.11)、配置平面大小、室內或室外環境、有無障礙物、Wi-Fi使用需求分布有無集中性與AP間的干擾等。綜合各議題，本論文討論一大型公共室內空間，公共空間之AP常設置於天花板中，因此AP處於一個電波有障礙之環境。並探討在此環境下，(i)行動障礙物的有無與(ii)使用需求分布是否具有集中性對一個與多個AP最佳配置之影響。

針對以上二議題，本研究分別建立問題的數學模型。在目標函數設計方面，我們以條件期望值做為最佳化指標，當使用者產生Wi-Fi使用需求所在位置位於AP訊號涵蓋範圍外之條件下，最小化使用者與AP之平均最短路徑；限制式則必須保持二個AP不互相干擾之安全距離以及障礙物區域無法配置AP。在Wi-Fi使用需求分布方面，我們以均勻分布表示當使用需求分布無集中性之情境；以有界高斯分布表示使用需求具有集中性之情境，我們將使用需求集中區域稱之為”精華區”，並討論不同的精華區累積機率與位置對AP最佳配置的影響。在行動障礙物方面，我們以方形障礙物做為室內隔間之代表，並比較有無障礙物AP最佳配置之差異性。

求解方法為使用MATLAB軟體從數值上找出各情境AP之最佳設置位置，並將無障礙物、Wi-Fi使用需求分布為均勻分布且配置一個AP下之數學解析解來比較，做為雙向驗證。經由數值模擬結果，在無障礙物之情境，在Wi-Fi使用需求為均勻分布或當精華區位於配置平面中心且累積機率不高時，配置一個AP之最佳位置皆位於配置平面之中心點；Wi-Fi使用需求為均勻分布下，當配置多個AP則最佳配置位置近似將配置平面等分成多個全等的矩形下，各矩形之中心點；Wi-Fi使用者需求為有界高斯分布下，若精華區累積機率較高時，AP最佳配置位置位於距離中心點AP訊號涵蓋半徑長之圓周上，而且，我們發現，此一特例與配置平面大小有關。經分析，理由與目標函數之設計有關。在存在障礙物之情境，無論使用需求分布為均勻分布或有界高斯分布，配置一個AP之最佳位置有遠離障礙物所在位置之趨勢，且AP訊號涵蓋範圍大於精華區面積時，使用需求為均勻分布之最佳配置位置與有界高斯分布之情境相同。

最後，我們依本論文之配置法，以台北市政府市政大樓一樓為模擬背景，估計實際大小找出其AP最佳配置位置，我們以有界高斯分布做為描述其Wi-Fi使用需求分布情況，並將其矩形四個角落之建築物缺角視為障礙物範圍。數值模擬結果接近於實際配置位置，並比較其設計目標之異同處，驗證本論文之研究結果具一定之實際性。

關鍵字

Wi-Fi ； AP最佳配置 ； Wi-Fi使用需求分布 ； 逐步配置AP ； 同時配置AP

並列摘要

The rise of Wi-Fi technology has solved the bandwidth demands of the wireless communication users in short distance. Wi-Fi is backward compatible with local area network above network layer, requires low cost of installation, making it prevalent in the areas like campuses, office buildings and residences. The designer determines location to set up Access Point (AP), quantity and channel to be used based on different design purposes. By observing the behaviors of Wi-Fi users, this thesis takes the user’s average moving distance as the optimization indicator of AP setup. It aims to find out the AP setup of the minimum average moving distance for the user, by considering the condition that the user can only access the Wi-Fi network by moving.

We discuss about the subjects related to AP setup first. There are several factors which affect the location to set up AP such as the setup quantity, the protocol standards of 802.11, the area of design plane, the indoor or outdoor environment, the obstacles, the centralization of Wi-Fi user distribution and the interference between APs. Based on these factors, we discuss a large public area indoors. In this area, AP is always installed in the ceiling so that it is located in environment with radio obstacles. Based on this environment, we analyze how (i)the existence of obstacles and (ii)the centralization of user distribution affect the optimal setup of a AP or multiple APs.

This research constructs mathematical models for these two mentioned topics respectively. In the aspect of designing objective function, we use the conditional expectation as an optimization indicator. When the user out of the AP signal area wants to access Wi-Fi network, we minimize the average shortest path between the user and AP. As for the constraints, we restrict that every AP pair should be located separately to keep a safe distance without any interference, and AP can’t be set up in area with obstacles. In the aspect of Wi-Fi user distribution, uniform distribution represents that the distribution of Wi-Fi access demands is not centralized, while truncated Gaussian distribution represents that the distribution of Wi-Fi access demands is centralized. Here we call the area with centralized access demands “Essential Area.” Then we discuss the influence of different cumulative probabilities and positions of essential areas on the optimal AP setup. In the aspect of mobile obstacles, we use square-shaped obstacles as the representative of the interior partitions. Moreover, we compare the difference of the optimal AP setup in the environment with or without obstacles.

As for the solution, we find the optimal AP setup locations in different scenarios by using MATLAB. Then we use analytic solution in mathematics to make a two-way verification in the scenario of no obstacles, uniform distribution and one installed AP. The simulation results show that the optimal setup locations of one AP are all in the center of a design plane on the condition that the Wi-Fi access demands are uniform distribution, or the essential area is in the center of the design plane and with low cumulative probability. Moreover, when Wi-Fi access demands are uniform distribution, we found that optimal setup locations of multiple APs are in the center of rectangles if the design plane is divided into several identical rectangles. When the Wi-Fi access demands are truncated Gaussian distribution, if the cumulative probability of the essential area is high, the optimal AP setup location is at the circle with the distance covered by the central AP signal as the radius. Moreover, we also find that this exception is related to the area of the design panel. According to the analysis results, it is because of the design of objective function. In the scenario with obstacles, no matter what the usage demands are uniform distribution or truncated Gaussian distribution, the optimal setup location of one AP tends to be far away from the obstacles. Moreover, when the area covered by the AP signal is bigger than essential area, the optimal setup locations are the same for both the usage demands being uniform distribution and truncated Gaussian distribution.

Finally, based on our design method, we find out the optimal setup location of one AP by estimating the area of Taipei City Hall as the simulation background. We describe the Wi-Fi usage demands by truncated Gaussian distribution and regard four rectangular corners as obstacle area. Our simulation results are close to the actual setup locations. Moreover, by comparing the differences between the possible design purposes, we verify that our research results are practical.

並列關鍵字

Wi-Fi ； optimal AP setup ； Wi-Fi access demands distribution ； setup APs sequentially ； setup APs simultaneously

參考文獻

[GaJ97]R. Ganesh and K. Joseph, “Effect of Non-Uniform Traffic Distributions on Performance of a Cellular CDMA System,” IEEE Universal Personal Communications, 1997

[JaH05]P. K. Jain and H. Haas, “Effects of User Distributions on CDMA System Performance,” IEEE Personal, Indoor and Mobile Radio Communications, 2005

[JWS03]Z. Jin, X. Wu, Y. Shu and F. Liu, ”Optimal Placement of Multiple 802.11b APs in a Wireless Classroom,” IEEE Electrical and Computer Engineering, 2003

[LKC02]Y. Lee, K. Kim and Y. Choi, “Optimal of AP Placement and Channel Assignment in Wireless LANs,” IEEE Local Computer Networks, 2002

[SFT10]S. Sendra, P. Fernanderz, C. Turro and J. Lloret, “IEEE 802.11a/b/g/n Indoor Coverage and Performance Comparison,” IEEE Wireless and Mobile Communications, 2010