實時工業物聯網的功率域非正交多址接入基站選址算法

孫 源，沈文建，倪朋勃，毛 敏，謝雅琪，徐朝農*

（1.中法渤海地質服務有限公司，天津 300450；2.中國石油大學（北京）信息科學與工程學院，北京 102249）

0 引言

在以油田為代表的大型工業生產現場，為了保證生產的安全順利進行，常常需要在現場安裝各種監控傳感器。這些傳感器監測生產數據，并實時傳輸給數據收集基站。通過對這些數據的處理，基站可以對危險情況加以判斷并實時處理，以確保生產的安全順利。

隨著技術的不斷進步，傳感器的數目越來越多，密度越來越大，出現了所謂的超密超可靠低延遲通信（massive Ultra-Reliable Low-Latency Communication，mURLLC）場景［1-3］。在這種場景下，數據傳輸擁擠現象越來越明顯，實時性能越來越難以保證。

在工業物聯網（Internet of Thing，IoT）場景下，無線網絡部分基本都為單跳網絡，此時網絡傳輸延遲基本為接入延遲，因此，對實時性能的優化基本都聚焦在接入延遲上。多用戶復用技術可用于降低接入延遲，提高網絡實時性［4-5］。除了傳統的頻分多路（Frequency Division Multiple Access，FDMA）、時分多路（Time Division Multiple Access，TDMA）、碼分多路（Code Division Multiple Access，CDMA）、正交頻分多路（Orthogonal Frequency Division Multiple Access，OFDMA）之外，基于串行干擾消除（Successive Interference Cancellation，SIC）技術［6-8］的功率域非正交多址接入（Power Domain NonOrthogonal Multiple Access，PD-NOMA）技術可以依賴接收功率的差異實現多用戶復用。考慮到當前mURLLC場景下的實際需求，目前第三代合作伙伴計劃（3rd Generation Partnership Project，3GPP）將其列為在物聯網場景下的待選接入標準，因此研究在PD-NOMA 技術下如何降低接入延遲顯然具有現實意義。大多數研究利用功率控制和用戶調度來實現低延遲［9］。例如，文獻［10］中通過聯合優化用戶調度和功率分配來解決基于k-SIC 的無線網絡的最小平均接入延遲問題，提出了啟發式算法，并證明其在2-SIC 和單位流量負載的情況下是最優的。文獻［11］中將延遲最小化問題表述為混合整數非凸規劃問題，該問題已被證明是NP-Hard。文獻［12］中針對多載波場景，研究了上行PD-NOMA 下最大完成時間的最小化問題，證明該問題也是NP-Hard，并提出基于最短處理時間的啟發式調度算法。除了調度式方法外，基于壓縮感知的隨機接入策略也可以達到降低接入延遲的目的［13］，但這種方法只適合于接入密度不大的場合。

傳統的使用PD-NOMA 技術來降低接入延遲的方法基本都基于功率調節來實現。然而在工業物聯網場景，尤其是一些電能獲取困難的場景下，傳感器端對功耗極為敏感，一般都存在發射功率受限的問題。這些低功耗的傳感器端的發射功率往往是不可調節的，因此傳統的PD-NOMA 調度方法并不適用這些場合。如何在嚴苛限制下實現接入延遲優化成為研究關鍵。事實上，對于PD-NOMA 技術而言，接收功率是決定能否實現多用戶復用的關鍵因素：當多個傳感器發射的信號在基站處的接收功率滿足一定差異性條件時可以實現并行接入，有利于降低接入延遲，而且傳輸復用越多，平均接入延遲越小。因此，通過調節數據收集基站與各個待接入無線傳感器的相對距離，也可以實現對接入延遲的優化。由于傳感器的位置一般來說是固定的，因此對數據收集基站的合理選址就成為優化接入延遲的必然選擇。本文針對工業物聯網中接入延遲較大的問題，提出一種實時工業物聯網的功率域非正交多址接入基站選址算法，該算法在工業場景下極具應用潛力。

需要注意的是，對于典型的工業物聯網系統來說，系統級的延遲性能實際是接入延遲、基站轉發延遲以及應用處理延遲等的總和，低的接入延遲是整個系統達到低延遲的基礎，因而本文只關注接入延遲。

1 網絡模型與問題描述

1.1 網絡模型

如圖1 所示，在工作區域內有n個單天線無線傳感器用戶S1，S2，…，Sn，每個傳感器的發送功率均為P且保持不變。這n個傳感器都有數據需要上傳，它們的位置已知且固定。以工作區域中心為原點建立極坐標系，對于傳感器Si，用二元組（xi，yi）來表示其位置；對于基站，則用（X，Y）來表示其位置；di表示基站到傳感器Si的距離，則

根據工業防爆的要求，例如基站之類的大功率設備只能安裝在離工作現場一定距離之外，本文限定基站只能安裝在指定的工作區域D，如圖1 所示。

圖1 問題模型Fig.1 Model of problem

無線信號經過空間傳輸必定會發生衰減，本文用Gi表示用戶的信道增益。對于工業場景，由于無線傳感器和基站一般不存在移動性，因此可以認為信號衰減只與距離有關，對于無線傳感器Si，當其距離基站的距離為di時，其信道增益為Gi=，接收功率rpi=pGi。其中：α代表信道衰減因子，其典型值區間為［2，4］；rpi代表基站處接收到的Si的信號功率。

由于工作在同頻同時，功率域非正交多址接入會引入用戶間的大的干擾，一般并不適合很大程度的用戶復用；因此，本文考慮迭代式SIC 接收機［14］，即基站最多同時可解的用戶無上限。在基站端，若用戶想要被成功解碼，則必須滿足：

其中：I為其他用戶對Si的干擾；n0代表高斯白噪聲；γ為接收機的接收信噪比閾值，常見值在2 dB 以上，對確知的解碼方式，其值是已知的。

在長期演進（Long Term Evolution，LTE）中，用戶終端（User Equipment，UE）通過物理上行控制信道上報自己的數據傳輸請求，然后由基站根據傳輸請求決定調度策略，并在物理上行共享信道中進行上行數據傳輸。與LTE 一致，假設一個時幀由多個時槽組成。根據工業物聯網的特點，為了保證傳輸公平性，每個無線傳感器將在一個時幀內僅被調用一次，這樣接入延遲就是時幀長度。可以明確的是：在最差的情況下，即每個時槽只被一個用戶獨占，也就是一個時幀最長不會超過n個時槽。

1.2 問題描述

基于1.1 節的網絡模型，本文的目的為最小化平均接入延遲，采用的基本手段是通過利用PD-NOMA 的并行接入能力，讓更多的無線傳感器并行傳輸。具體的手段為聯合數據收集基站的位置設置（X，Y）和傳感器傳輸時刻配置｛Nij｝。

其中：式（4）中的Nij是調度決策，用于保證一個無線傳感器在一幀里只能傳輸一次，Nij=1 表示無線傳感器Si在時槽j時被調度傳輸；式（5）～（6）用于保證用戶可以被SIC 接收機基站解碼；式（7）為信道增益模型；式（8）則確保基站處于安全的安裝位置。優化目標為最小化對應策略的幀長。顯然，上述優化式的控制變量為基站的位置和調度決策。

2 問題求解

根據1.2 節，該問題是一個組合優化問題，因此尋找低復雜度的算法相對困難，需要設計啟發式的搜索算法。有序合理的搜索會在很大程度上降低實際的復雜度，這就需要尋找一個合理的啟發式策略［14］。本文的思路是：在可行區域內，選擇出有限個相較于其他區域可支持更多的用戶復用的候選區域；然后對每個候選區域，給出其最佳傳輸調度策略；最后通過簡單比較得出幀長最短的調度策略所對應的候選區域，即為最佳基站位置。

2.1 基站候選區域尋找

根據文獻［10，15］，上述問題很可能是一個NP 完全問題［14］，難以找到最優解；而其主要難點在于式（5），式（5）中的n0造成并行用戶的接收功率不能成比例，會給后面的解析推導帶來困難，這也是在定理1 中提出縮放的根本原因。為了能夠快速求出一個近似解，本文并沒有采用如文獻［16］的搜索算法，而是按照定理1 中的條件對約束式（2）進行了適度的收緊。需要注意的是，這種收緊并不能保證得到最優解，而可能得到次優解；因此這個低復雜度的解法本質上是一個啟發式算法［15］。在仿真實驗結果可以看到，這種稍微的約束收緊對算法性能影響極其有限。

然后，對任意一個無線傳感器有序對，現在求其基站可解碼區域。顯然，如果有n個無線傳感器，最多可以找到n(n-1)個基站可解碼區域，這些基站可解碼區域都是圓形。由于凸集間的交集仍是凸集，因此多個基站可解碼區域相交形成的區域必定為凸區域，且凸區域最多不會超過n(n-1)個。相較于其他區域，基站位于這些區域時將會支持更多的傳輸復用（這些區域被稱為基站候選區域），這就為下一步的實時調度策略留下了更大的優化空間。如圖2 所示，該網絡包含了3 個無線傳感器S1、S2、S3和1 個NOMA 數據收集基站，通過畫出6 個有序的節點對對應形成的基站可解碼區域為（圖2 中的白色區域）；求取這些區域的最小相交凸區域，從而得到了2 個基站候選區域 ：和（圖2 中的深色區域）。

圖2 基站可解碼區域與基站候選區域示例Fig.2 Example of decodable area and candidate area of sink

2.2 尋找單個基站候選區域下的最短幀長

對于每個基站候選區域，為了使當把數據收集基站放在該區域時的幀長最短，可采用具體方法如下：對于每一個候選區域，建立一個生成圖G=，它是一個頂點集為V={S1，S2，…，Sn}的有向無環圖，其中n為無線傳感器的個數。對于圖中任意兩個節點Si、Sk，若基站處于該候選區域內時對Si的接收功率rpi和對Sk的接收功率rpk滿足rpirpk≥1+γ，則E中對應有一條由Si到Sk的有向邊。進而，尋找最短幀長問題就等價于生成圖的最小鏈劃分問題。定理2 說明了它們之間的等價性。

定理2生成圖上的每條有向鏈對應著一組可解碼序列。

證明 由定理1 可知，若一組無線傳感器的接收功率rp1，rp2，…，rpm滿足rpirpi+1≥1+γ（i=1，2，…，m-1），此時所有傳感器可在基站端同時解碼。由生成圖的構造過程可知，生成圖中的每一條有向邊（如SiSk），當基站處于候選區域內時都會滿足rpirpk≥1+γ。因此對于生成圖的任意一條有向鏈來說，由于傳遞性的原因，其上的所有無線傳感器節點在基站處的接收功率一定滿足定理1 的條件。從而，它們形成了一條可解碼序列。證畢。

圖3 生成圖的有向鏈與可解碼序列的對應Fig.3 Correspondence between directed chain of generation graph and decodable sequence

鑒于一條可解碼序列將占用一個時槽，為了得到在確定基站位置下的最短調度，顯然要尋找生成圖的最小鏈劃分。最短幀長則為最小鏈劃分數。

定義1有向圖的最小鏈劃分。在有向無環圖G中，選擇若干條無公共點的有向鏈，使得這些鏈覆蓋所有節點，且鏈的條數最小。

對于給定的有向圖來說，最小鏈劃分問題可通過Dilworth 定理求解，該算法的復雜度為O(|V||E|)。圖4 給出了一個生成圖的最小鏈劃分，以及該鏈劃分對應的調度策略。

圖4 中，對于給定的有向無環圖，通過Dilworth 定理找到其最小鏈劃分：S1-S3-S6-S8、S4-S6-S9、S2-S5-S10，從而表示S1、S3、S6、S8可安排在同一個時槽發送，S4、S7、S9可安排在同一個時槽發送，S2、S5、S10可安排在同一個時槽發送，因此最小幀長為3。

圖4 最小鏈劃分及其對應的調度策略Fig.4 Minimum chain partitioning and corresponding scheduling strategy

2.3 算法描述

在2.2 節，當基站處于某個候選區域時，可以尋找到此情況下的最短調度策略。本節中，對于所有的候選區域的最短調度策略，通過直接比較它們的最短調度策略的幀長并選取幀長最小的調度策略就是最優的調度策略，其對應的基站候選區域即為最優基站位置。問題求解算法可描述如下。

對上述算法做簡要描述：在初始化以后，算法2）～4）行求出所有的基站可解碼區域；第5）行由基站可解碼區域集得到基站候選區域集；第6）～7）行為每個基站候選區域建立生成圖，并基于二部圖匹配算法求出在該基站候選區域下的最優調度策略；第8）行在上述所有的生成策略中選擇幀長最短的調度策略，該策略對應的基站候選區域則為基站的最優位置。

對每個候選位置計算調度策略的時間復雜度是O（nE），其中E為生成圖的邊數，由于候選位置個數不超過n(n-1)個，所以算法的復雜度為O（n3E）。

需要說明的是，如果基站可解碼區域集為空，則表示傳感器之間無法利用PD-NOMA。此時，基站只要能保證和每個傳感器能通信即可，此時實時性最強的傳輸方案就是TDMA。

3 實驗與結果分析

在100 m × 100 m 的正方形工作區域內隨機放置一定數量（10 到30 不等，具體數量根據實驗設置）的無線傳感器節點，傳感器的發送功率設為2 dBm，通信帶寬為180 kHz。接收機噪聲為加性高斯白噪聲，其功率譜密度為-169 dBm/Hz，因此噪聲的平均功率為-117 dBm，不再考慮其他干擾源。接收機解碼閾值范圍設為［3，6］ dB。信道衰減因子為［2，4］。基站允許的建造區域是一個400 m × 400 m 的正方形區域，其中心點與工作區域的中心點重合。每次實驗重復算法100 次。

實驗1 研究平均幀長度和信道衰減因子、解碼閾值的關系。實驗1 的結果見圖5，可以看出平均幀長度隨著信道衰減因子的增加而呈近似線性的減小。這是因為功信道衰減因子增加時，接收到的用戶之間的功率差也會增大；因此兩個用戶的可解碼區域面積增加，圓形區域之間交叉的可能性也增加，從而導致生成圖中出現更多的邊，使得幀長減小。

圖5 平均幀長度和衰減因子與解碼閾值的關系Fig.5 Relationship between average frame length，decay factor and decoding threshold

實驗2 研究平均幀長度和傳感器數目（用戶數）的關系。圖6 比較了不同用戶數下的算法性能。參數設置如下：傳感器數目為［10，30］，功率衰減因子為2，所有用戶隨機分布。事實上，實驗所得到的最短幀長度與用戶數的比值基本上是固定的，換句話說，每個用戶的延遲基本上不受用戶數的影響。這可以從一定程度上說明調度策略已經非常接近最優，沒有進一步優化的空間了。從圖6 也可以看出平均幀長度隨著解碼閾值的增加而呈近似線性的減小，其原因與實驗1 是類似的。

圖6 平均幀長度與傳感器數量的關系Fig.6 Relationship between average frame length and number of sensors

實驗3 研究平均幀長度和拓撲方式的關系。實驗3 進一步探討了傳感器的位置分布對幀長度的影響，實驗結果見圖7。除了隨機布設之外，本文還設計了幾種不同的傳感器位置分布。圖例中的n是用戶數，3×10 表示用戶按等間隔排列為3 行和10 列，以此類推。顯然，不同的傳感器布設方式對于平均幀長度是有影響的；并且當用戶以等間隔的線性排列時，最小幀長度比在隨機布設的情況下短；此外，在該等間隔線性排列下，基站的最優位置是在線性排列的兩端附近。造成此現象的原因是：當基站處于線性排列的兩端時，基站接收到的無線傳感器的接收功率與其他拓撲相比差異更為顯著，傳感器傳輸之間的組合靈活性大幅增加。因此本文算法可以更靈活地組合不同的傳輸，從而帶來更低的延遲性能。

圖7 平均幀長度和傳感器布設方式的關系Fig.7 Relationship between average frame length and layout of sensors

以隨機拓撲為代表，由圖7 可知，當解碼閾值為2，n為30 時，最少需要11 個時槽（因為高斯白噪聲的方差是隨機的，因此會出現不為整數的情況），也就是說，接入延遲降低為TDMA 時的36.7%；n為20 時，最少需要7 個時槽，接入延遲降低為TDMA 時的35%，接入延遲性能顯著提升。

4 結語

PD-NOMA 技術支持多路并行接入，因此對于工業物聯網應用的延遲性能有重大影響，可能會成為未來工業物聯網的物理層標準。在此技術平臺下，針對接入延遲最小化進行了研究，提出了基于基站選址方法來降低接入延遲。該方法能夠應用在很多實際場合，具有現實的意義。隨著未來第五代移動通信技術（5th Generation mobile communication technology，5G）R17 標準的不斷發展和mURLLC 應用場景的不斷發掘，對于低延遲的需求以及相應的技術和算法必將越來越迫切，必將是未來的研究重點之一。