實(shí)時(shí)工業(yè)物聯(lián)網(wǎng)的功率域非正交多址接入基站選址算法

孫 源，沈文建，倪朋勃，毛 敏，謝雅琪，徐朝農(nóng)*

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

0 引言

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

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

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

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

需要注意的是，對于典型的工業(yè)物聯(lián)網(wǎng)系統(tǒng)來說，系統(tǒng)級的延遲性能實(shí)際是接入延遲、基站轉(zhuǎn)發(fā)延遲以及應(yīng)用處理延遲等的總和，低的接入延遲是整個(gè)系統(tǒng)達(dá)到低延遲的基礎(chǔ)，因而本文只關(guān)注接入延遲。

1 網(wǎng)絡(luò)模型與問題描述

1.1 網(wǎng)絡(luò)模型

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

根據(jù)工業(yè)防爆的要求，例如基站之類的大功率設(shè)備只能安裝在離工作現(xiàn)場一定距離之外，本文限定基站只能安裝在指定的工作區(qū)域D，如圖1 所示。

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

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

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

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

在長期演進(jìn)（Long Term Evolution，LTE）中，用戶終端（User Equipment，UE）通過物理上行控制信道上報(bào)自己的數(shù)據(jù)傳輸請求，然后由基站根據(jù)傳輸請求決定調(diào)度策略，并在物理上行共享信道中進(jìn)行上行數(shù)據(jù)傳輸。與LTE 一致，假設(shè)一個(gè)時(shí)幀由多個(gè)時(shí)槽組成。根據(jù)工業(yè)物聯(lián)網(wǎng)的特點(diǎn)，為了保證傳輸公平性，每個(gè)無線傳感器將在一個(gè)時(shí)幀內(nèi)僅被調(diào)用一次，這樣接入延遲就是時(shí)幀長度?？梢悦鞔_的是：在最差的情況下，即每個(gè)時(shí)槽只被一個(gè)用戶獨(dú)占，也就是一個(gè)時(shí)幀最長不會超過n個(gè)時(shí)槽。

1.2 問題描述

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

其中：式（4）中的Nij是調(diào)度決策，用于保證一個(gè)無線傳感器在一幀里只能傳輸一次，Nij=1 表示無線傳感器Si在時(shí)槽j時(shí)被調(diào)度傳輸；式（5）～（6）用于保證用戶可以被SIC 接收機(jī)基站解碼；式（7）為信道增益模型；式（8）則確?；咎幱诎踩陌惭b位置。優(yōu)化目標(biāo)為最小化對應(yīng)策略的幀長。顯然，上述優(yōu)化式的控制變量為基站的位置和調(diào)度決策。

2 問題求解

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

2.1 基站候選區(qū)域?qū)ふ?/h3>

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

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

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

2.2 尋找單個(gè)基站候選區(qū)域下的最短幀長

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

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

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

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

鑒于一條可解碼序列將占用一個(gè)時(shí)槽，為了得到在確定基站位置下的最短調(diào)度，顯然要尋找生成圖的最小鏈劃分。最短幀長則為最小鏈劃分?jǐn)?shù)。

定義1有向圖的最小鏈劃分。在有向無環(huán)圖G中，選擇若干條無公共點(diǎn)的有向鏈，使得這些鏈覆蓋所有節(jié)點(diǎn)，且鏈的條數(shù)最小。

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

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

圖4 最小鏈劃分及其對應(yīng)的調(diào)度策略Fig.4 Minimum chain partitioning and corresponding scheduling strategy

2.3 算法描述

在2.2 節(jié)，當(dāng)基站處于某個(gè)候選區(qū)域時(shí)，可以尋找到此情況下的最短調(diào)度策略。本節(jié)中，對于所有的候選區(qū)域的最短調(diào)度策略，通過直接比較它們的最短調(diào)度策略的幀長并選取幀長最小的調(diào)度策略就是最優(yōu)的調(diào)度策略，其對應(yīng)的基站候選區(qū)域即為最優(yōu)基站位置。問題求解算法可描述如下。

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

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

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

3 實(shí)驗(yàn)與結(jié)果分析

在100 m × 100 m 的正方形工作區(qū)域內(nèi)隨機(jī)放置一定數(shù)量（10 到30 不等，具體數(shù)量根據(jù)實(shí)驗(yàn)設(shè)置）的無線傳感器節(jié)點(diǎn)，傳感器的發(fā)送功率設(shè)為2 dBm，通信帶寬為180 kHz。接收機(jī)噪聲為加性高斯白噪聲，其功率譜密度為-169 dBm/Hz，因此噪聲的平均功率為-117 dBm，不再考慮其他干擾源。接收機(jī)解碼閾值范圍設(shè)為［3，6］ dB。信道衰減因子為［2，4］?；驹试S的建造區(qū)域是一個(gè)400 m × 400 m 的正方形區(qū)域，其中心點(diǎn)與工作區(qū)域的中心點(diǎn)重合。每次實(shí)驗(yàn)重復(fù)算法100 次。

實(shí)驗(yàn)1 研究平均幀長度和信道衰減因子、解碼閾值的關(guān)系。實(shí)驗(yàn)1 的結(jié)果見圖5，可以看出平均幀長度隨著信道衰減因子的增加而呈近似線性的減小。這是因?yàn)楣π诺浪p因子增加時(shí)，接收到的用戶之間的功率差也會增大；因此兩個(gè)用戶的可解碼區(qū)域面積增加，圓形區(qū)域之間交叉的可能性也增加，從而導(dǎo)致生成圖中出現(xiàn)更多的邊，使得幀長減小。

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

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

圖6 平均幀長度與傳感器數(shù)量的關(guān)系Fig.6 Relationship between average frame length and number of sensors

實(shí)驗(yàn)3 研究平均幀長度和拓?fù)浞绞降年P(guān)系。實(shí)驗(yàn)3 進(jìn)一步探討了傳感器的位置分布對幀長度的影響，實(shí)驗(yàn)結(jié)果見圖7。除了隨機(jī)布設(shè)之外，本文還設(shè)計(jì)了幾種不同的傳感器位置分布。圖例中的n是用戶數(shù)，3×10 表示用戶按等間隔排列為3 行和10 列，以此類推。顯然，不同的傳感器布設(shè)方式對于平均幀長度是有影響的；并且當(dāng)用戶以等間隔的線性排列時(shí)，最小幀長度比在隨機(jī)布設(shè)的情況下短；此外，在該等間隔線性排列下，基站的最優(yōu)位置是在線性排列的兩端附近。造成此現(xiàn)象的原因是：當(dāng)基站處于線性排列的兩端時(shí)，基站接收到的無線傳感器的接收功率與其他拓?fù)湎啾炔町惛鼮轱@著，傳感器傳輸之間的組合靈活性大幅增加。因此本文算法可以更靈活地組合不同的傳輸，從而帶來更低的延遲性能。

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

以隨機(jī)拓?fù)錇榇?，由圖7 可知，當(dāng)解碼閾值為2，n為30 時(shí)，最少需要11 個(gè)時(shí)槽（因?yàn)楦咚拱自肼暤姆讲钍请S機(jī)的，因此會出現(xiàn)不為整數(shù)的情況），也就是說，接入延遲降低為TDMA 時(shí)的36.7%；n為20 時(shí)，最少需要7 個(gè)時(shí)槽，接入延遲降低為TDMA 時(shí)的35%，接入延遲性能顯著提升。

4 結(jié)語

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