【正文】 ， V = {v1, … , vn} 是網絡中 n個節(jié)點（ MR和 IGW）的集合，其中 m個是 IGW，其余為普通 MR， m (n–m ) 。 ? 每個 MR節(jié)點（ vi）配置一組射頻無線接口，用 ρ(vi)={1, 2, … , |ρ(vi)| }表示，同一個節(jié)點的不同射頻接口配置在不同的信道上。 ? 集合 CH = {1, 2, … , c}代表無線系統(tǒng)中 c個不重疊的信道。 ? 信道 i∈ CH上可能的數(shù)據速率用 wi bit/s表示。 ? MR用于骨干連接的射頻傳輸距離均為 Rtran，當且僅當兩個節(jié)點之間的距離小于通信距離時，它們之間存在一條邊。 E = {e1, … , ek}為邊集。 ? 給定一個 MR vi∈ V，其流量可能包括兩部分： 1）本地因特網流量 Tl (vi)，由其服務區(qū)內的移動用戶產生； 2）中繼因特網流量 Tr (vi)，為其它 MR轉發(fā)的流量。 ? 部署完成后，節(jié)點 vi∈ V的物理位置固定，每個節(jié)點都有持續(xù)的電源供應，IGW的有線連接及因特網帶寬 j是無限的， IGW成本比 MR高。 問題描述 ? IGW放置問題定義為： ? 給定一個具有 n個 MR的網絡，從中選擇 m個節(jié)點 I = {I1, … , Im }，使得 WMN能夠滿足每個 MR的因特網流量需求（即 Tl (vi)）。 ? IGW放置問題需要滿足以下約束條件： ? 全覆蓋：每個 MR至少連接到一個 IGW上（通過一跳或多跳路徑）。 ? IGW的吞吐能力：網絡中所有 IGW的吞吐能力之和不小于網絡中總的流量需求： ? MR的吞吐能力：通過一個 M（ vi ） R的流量不能超過它的吞吐能力： ? 共信道干擾（ cochannel interference）： IGW和 MR的吞吐能力受干擾影響。 ? 投資成本 干擾模型 ? 理想鏈路模型： ? 如果路徑的跳數(shù)不超過一個給定值，路徑吞吐量不下降；超過該給定值，吞吐量為 0。 ? 基于跳數(shù)的吞吐量下降模型： ? 從 MR vi到一個 IGW的長為 p跳的路徑，為獲得的吞吐量 Tl (vi)，實際需要的吞吐量 T’l (vi, p) 可用下式估算，其中 α為每跳多消耗的吞吐量比例： ? 基于碰撞的模型： ? 令 Rint為一個信道的干擾范圍（ Rint Rtran），在這個范圍內信道不能被重用， Wint為在該范圍內使用信道的最大吞吐量。若使用多個正交信道，則 Wint是在 Rint范圍內使用所有正交信道的最大吞吐量。 優(yōu)化目標 ? 最小化 IGW的數(shù)量： ? 確定 IGW的位置，使得用最少數(shù)量的 IGW提供足夠的網絡吞吐能力。 ? 最小化 MRIGW的跳數(shù)： ? 研究表明，每個節(jié)點可獲得的吞吐量 λ為： ? 當使用多個信道時， ? 因此， IGW的放置應使得 MRIGW的平均跳數(shù)最小。 ? ）可承受的計算復雜度： ? 尋找 IGW的最佳放置是一個 NP難的問題。 WMN網絡架構與 IGW放置 ? 為了有效部署 WMN，提出了一些 WMN架構，以下為 [6]介紹的兩種： ? IGW指向和連接的簇 ? 以 IGW為根的樹 （ 1） IGW指向和連接的簇 ? 一個 IGW指向和連接的簇是一個連通圖 Clusteri = ( Vi, Ei )，其中 Vi = {Ii, v1’, … , vi’}， Ii是簇頭， v1’, … , vi’為 MR， Ei = {e1’, … , ei’}是指向 IGW Ii的邊集。 ? IGW指向和連接的簇是一個有向圖 G’，它具有以下特性： ? Clusteri為無環(huán)連通圖，簇頭為所選擇的 IGW； ? 每條邊均從一個 MR指向 IGW； ? 每個 MR通過一跳或多跳連接到 IGW，一個 MR可以有多條路徑指向 IGW； ? 給定 n個節(jié)點的一個初始 WMN，可以將網絡劃分成 m個不相交的簇，每個簇的簇頭為一個 IGW，每個 IGW有能力滿足本簇內所有MR的流量需求。 圖示 （ 2）以 IGW為根的樹 ? 以 IGW為根的樹是一棵連通樹，所有的邊指向作為根節(jié)點的 IGW。 ? 基于樹的 WMN由以 IGW為根的樹組成。 ? 尋找最小數(shù)目 IGW的設計目標轉化為尋找最小數(shù)目的以 IGW為根的樹，同時每個 IGW能夠滿足樹中所有節(jié)點的流量需求。 ? 前面的約束條件轉化為： ? IGW吞吐能力的限制轉化為對樹的規(guī)模限制： ? 前兩個干擾模型轉化為對 MRIGW跳數(shù)的限制 ? 中繼負載的限制： IGW放置的線性規(guī)劃描述 參考文獻 [1] Ian F. Akyildiz, et, al. A Survey on Wireless Mesh Networks. IEEE Radio Communications. Sep. 2022. [2] Krishna N. Ramachandran, et, al. On the Design and Implementation of Infrastructure Mesh Networks. IEEE workshop on Wireless Mesh Networks, 2022. [3] P. Gupta, and P. Kumar. The Capacity of Wireless works. IEEE Trans. Info. Theory. , , . [4] Yaling Yang, Jun Wang, and Robin Kravets. Designing Routing Metrics for Mesh Networks. IEEE Workshop on Wireless Mesh Networks, 2022. [5] Liang Ma, and Mieso K. Denko. A Routing Metric for LoadBalancing in Wireless Mesh Networks. AINAW’07, 2022. [6] Bing He, et, al. Optimizing deployment of Inter gateway in Wireless Mesh Networks. Computer Communications, 31(2022). [7] A. Raniwala, and T. Chiueh. Architecture and Algorithms for an IEEE multichannel wireless mesh work. Info’05. [8] S. Waharte, and R. Boutaba. Treebased Wireless Mesh Network Architecture: Topology Analysis. MeshNets’05.