0 引言

    作為5G通信的關鍵候選技術之一^[1]，D2D通信技術可以實現基于鄰近服務設備之間的直接通信要求，具有降低服務基站負荷的優勢。D2D發現過程作為D2D通信中實現基于鄰近服務的第一步，是以設備對之間安裝有相同且同處于激活狀態的應用程序^[2]為前提來實現的。傳統上進行D2D發現過程所使用的發現消息是基于應用程序名稱設計的，這樣不僅使得內存方面不能滿足日益增長的數據要求，而且也使得數據傳輸速率方面有所欠缺。

    因此，對此問題的相關文獻也不斷涌現。文獻[3]提出了一種基于hash函數來進行發現消息的構造的方案。文獻[4]在文獻[3]的基礎上添加使用bloom濾波器來進行發現消息的構造，方案中，發現消息基于bloom過濾器數據結構和K個hash函數來設計。由文獻[3]、[4]所述，在應用程序發現的過程中，假肯定情況是不可避免的，而且，降低錯誤的概率則會顯著增加發現信息的大小。

    由此，本文提出了基于RLE編碼二叉樹發現消息的設計。發現消息中使用應用程序的標識值范圍而不是標識值來減少發現消息的大小，隨后通過使用二叉樹^[5-6]來表示分頁的范圍，并通過RLE編碼^[5]的二叉樹的比特信息來通知作業設備應用程序的值范圍，以此實現高效無誤的設備對發現過程。

1 發現過程及其模型

    為了方便標識設備中各個應用程序，本文采用應用程序名稱對應的ASCII值的總和作為其標識值。因為各個應用程序的名稱不相同，所以標識值可以唯一標識各個應用程序。統計當下設備中各個應用程序的名稱，發現所占字節數如圖1所示。

    從普遍性的角度，可用72個比特來標識各個應用程序的名稱。假設在某個發現周期中，作業應用程序的個數為n，非作業應用程序的個數為m，n≥1，m≥0，那么在發現周期中所涉及到的應用程序的總數為L=n+m，假定應用程序標識值的最大值為M，M=2⁷²，那么作業應用程序的分頁范圍的最大長度就為M，最小長度為1。特定發現周期中的所有分頁范圍構成分頁集合Gp，其互補集合就是未分頁區域的值范圍。

    實際上，發現消息就是經過RLE編碼之后的分頁集合G_p的標識之一。

2 發現消息設計

    本文提出的基于RLE編碼的二叉樹方法，通過一個經過RLE編碼的分頁二叉樹T_p來唯一地表示這種分布，且一個T_p對應一個Gp^[6]。下面介紹具體過程。

2.1 發現消息二叉樹的構造

    設備在發現周期中可以根據應用程序標識值唯一地創建發現消息二叉樹。當通過二叉樹表示分頁范圍時，迭代中點細分法用于將整個值范圍[0，M-1]劃分為不確定長度的多個節點，如a∈{M，M/2，M/4，M/8，…}。在迭代細分過程中，若每個劃分范圍只包含非作業的應用程序或作業的應用程序，則結束此過程；若較小（較大）范圍不包含作業應用程序和非作業應用程序，則執行較小（較大）范圍的中點進行迭代細分。每個細分操作伴隨著在現有二叉樹上添加一個左（右）節點，并將一個根節點進行初始化。以此類推，直到沒有范圍包含作業或非作業應用程序后，完成發現消息的二叉樹的構造。

    基于上述過程，設備可以通過算法1為特定G_p構造一顆二叉樹。

    算法1：

    (1)設置初始搜素范圍[x，y]，其中x=0，y=M-1，將當前節點設置為根節點；

    (2)對于搜索范圍[x，y]，通過中點二分法分成兩部分，分別為[x，(x+y)/2]和[(x+y)/2，y]；

    (3)若較小（大）范圍僅包含作業應用程序標識，則不進行下一步劃分。一個葉節點和一個邊緣被添加到當前節點的左（右）側；

    (4)若較小（大）范圍僅包含非作業的應用程序標識值，則不進行下一步劃分。在當前節點的左（右）側不添加節點；

    (5)若較小（大）范圍包含兩種不同的應用程序標識值，那么進行下一步的劃分。在當前節點的左（右）側添加一個節點和一個邊緣，并且將搜索范圍改為[x，(x+y)/2]和([(x+y)/2，y])，進行步驟(2)的操作；

    (6)若沒有范圍進一步劃分，那么發現消息二叉樹構造完成，否則，轉到步驟(2)。

2.2 發現消息的構造

    為了便于在無線信道中實現D2D通信過程,本文進行了消息二叉樹轉換二進制比特串的過程。

    由2.1節可知，根據節點的度數和連接性可以將節點劃分為以下4種不同的類型：

    (1)具有左和右子樹/葉節點的節點；

    (2)只有左子樹/葉節點的節點；

    (3)只有右子樹/葉節點的節點；

    (4)葉節點本身。

    因此，可以根據表1所示的原理將每個節點用兩個比特來表示，并依據二叉樹遵循寬度優先的遍歷準則，按順序輸出每個節點的兩位以形成二進制比特串，隨后通過算法2使用的RLE編碼將比特串編碼為最終的發現消息。

    由于該比特串中只含有‘0’和‘1’兩種不同的數值，所以可以使用兩個字節來進行發現消息的RLE編碼的過程。

    算法2：

    (1)計算比特串長度值，初始化計數變量和位置指針，并讀取由算法1生成的比特串；

    (2)對比循環讀取的值與當前要進行RLE編碼的值：

    ①若相等，計數器加1，位置指針加1，直到不相等的數值出現，按照計數值在前數值在后的規則，進行發現消息的構造,進行步驟(3)；

    ②否則，直接存儲該值到發現消息中，并將位置指針加1，進行步驟(3)；

    (3)若讀取到比特串的末尾處，則結束程序；

    (4)結束程序，完成發現消息的構造。

    由此，設備中的應用程序可以根據發現消息的比特串來判斷自身是否被激活。首先，設備通過RLE進行比特串的解碼，然后按照寬度優先準則，將比特串轉化為一棵二叉樹，隨后判斷設備中的應用程序標識值是否屬于由該二叉樹表示的集合，僅當其標識值屬于該集合時，才可認為含有此應用程序的終端就是目標設備，具體的判斷方法如下：

    (1)首先，接收到經過RLE編碼的比特串；

    (2)循環讀取當前的數值val，若val≠0且val≠1，則按照此數值將其后的值補充為val進行顯示；若val=0或val=1，則按原值顯示；

    (3)初始化節點的取值范圍，起始和結束位置為Start=0和end=0，將當前的判斷節點視為根節點；

    (4)對于每個當前判斷的節點，設備中的應用程序都應判斷其標識值是否屬于該節點指示的范圍；

    (5)若當前判斷節點為葉節點，則認為設備中的此應用程序是作業的，退出判斷過程。否則，設置中點為mid=(Start+end)/2；

    (6)如果當前判斷的標識值>mid；

    ①若當前節點的右子樹存在，那么設置Start=mid，將其右子樹的根節點為當前判斷節點，執行步驟(2)；

    ②否則，即不存在右子樹，那么設備認為它沒有要被作業的應用程序；

    (7)如果判斷的標識值<mid；

    ①若當前節點的左子樹存在，設置end=mid，將該節點的左子樹的根節點為當前判斷節點，執行步驟(2)；

    ②否則，退出程序；

    (8)結束程序。

    綜上所述，發現消息是被復制到一個二進制比特串中的，這樣可以達到減少發現消息大小的目的。同時由于使用比特串，所以即使存在大量的作業應用程序，所提出的方法也不會出現假肯定性錯誤^[4]。而且就其復雜度而言，它與二進制搜索算法一樣高效的。

3 性能分析

    發現消息的理想設計是通過最短的消息發現大量的設備，并且不會出現錯誤率。基于上述分析，所提出的發現消息可以精確指示多個應用程序。此外，本文所提出的設計性能取決于設備中作業和非作業應用程序的數量。

    由于分頁二叉樹上的每個節點由兩個比特表示，因此首先分析的是二叉樹上的節點的期望數量。假設在[0，M-1]分布范圍內有L個應用程序，由于發現消息二叉樹是基于應用程序標識值的不同分布而變化的，因此期望函數E(M，n，m)被定義為發現二叉樹中的期望節點數，其中M≥n+m，n≥1。根據節點的不同特征，本文采用遞歸分析的方法計算E(M，n，m)。假設在范圍[0，M-1]中存在n個作業和m個非作業應用程序，那么在此情況下構造的特定二叉樹的概率被定義為P(M，n，m，i，j)，含義：在該特定二叉樹中，由根節點的左子樹表示的范圍包含i個作業和j個非作業應用程序，而由右子樹表示的范圍內包含n-i個作業和m-j個非作業應用程序。表2給出了不同特定二叉樹的節點數和其概率。

    那么，二叉樹中的總節點數分為一個根節點和左、右子樹中節點數的總數。左子樹和右子樹中的預期節點數可以分別表示為E(M/2，i，j)和E(M/2，n-i，m-j)。

    基于統計期望的定義，表2中列出的其他情況也可以以相同的方式來進行分析。對于初始情況，則E(2，1，1)=2和E(M，n，0)=1，其中n≥1，m=0，M>2。

    由表2可得發現二叉樹的節點統計期望：

    由于作業應用程序的數量遠小于總的應用程序的數量，本文中，只考慮n≤M/2的情況，對于某個m，m≥n，那么節點數量最大的概率為：

    假定消息二叉樹的節點數為式(2)中的E(M，n，m)，那么該E(M，n，m)所對應的信息如表3所示。

    由文獻[5]可得，在不失一般性的情況下，假定在比特串中某一位置出現0的概率為p，0≤p≤1，那么出現1的概率為1-p；以此類推，長度為p的0游程出現的概率為p^l(1-p)，長度為l的1游程出現的概率為p(1-p)^l。

    在本文中，某一位置出現0的概率為：

    比較式(4)、式(5)可得，所提出的方法可以顯著減少統計標準中的發現消息大小。這在后續的仿真結果中可以得到進一步的驗證。

    發現消息的大小是實現高效D2D通信的關鍵問題之一^[7]，因此本文通過研究發現消息大小的方式來評估所提方法的性能。圖2顯示了所提方案在不同作業應用程序下的累積分布圖，由該圖可得在90%的仿真結果中，所提方案可以在較小比特長度的情況下，能夠很好地發現作業的應用程序；由圖3可以得出，所提方案中的發現消息大小優于其他3種方案。傳統方案中，由于發現消息是含有全部應用程序的名稱，其大小為72n bit，與傳統方案相比，其余3種方案對于發現消息減少方法都實現了顯著的增強。而且所提方案相比于bloom方案存在的假肯定性錯誤和比特個數而言，它的效果顯然是更優的。并且本文所提方案在二叉樹的基礎上又進行了一次RLE編碼，更好地實現了縮短發現消息大小的目的。

4 結論

    本文提出了一種通過減少發現消息大小來解決D2D通信系統中發現容量問題的新方法。經過RLE編碼的發現消息二叉樹被設計為指示作業應用程序的標識范圍，這要比傳統機制中攜帶作業應用程序的名稱列表更為有效。而且經過理論分析和仿真模擬可得，預期發現消息的大小得以顯著減少。因此，本文提出的方法增加了D2D通信系統的發現能力，能夠支持大量的設備通信。對于未來的工作，所提出的方案還可以被優化，以便處理消息尺寸超重這一個罕見的情況。

參考文獻

[1] ASADI A，Wang Qing.A survey on Device-to-Device communication in cellular Networks[J].Arash IEEE Communications Surveys and Tutorials，2014，16(4)：1801-1809.

[2] 董自強，劉燦燦.基于鄰近服務的D2D節點發現技術綜述[J].微型機與應用，2016，35(16)：60-62，66.

[3] CHOI K W，LEE H，CHANG S C.Discovering mobile applications in Device-to-Device communications：Hash function-based approach[C].2014 IEEE 79th Vehicular Technology Conference(VTC Spring)，2014：1-5.

[4] CHOI K W，WIRIAATMADJA D T.Discovering mobile applications in cellular Device-to-Device communications：Hash function and bloom filter-based approach[J].IEEE Transaction on Mobile Computing，2016，15(3)：336-349.

[5] 周愛武，吳國進，崔丹丹.一種改進的二叉樹多分支持向量機算法[J].微型機與應用，2011，30(6)：14-21.

[6] Shi Yulong，Xi Wei，Zhou Hua.Effiicient paging message design based on binary tree in NB-IoT system[C].IEEE Conference on Standards for Communicaions and NetWorking(CSCN)，2016：1-6.

[7] CHOI K W，Zhu Han.Device-to-Device discovery for proximity-based service in LTE-advanced system[J].IEEE Journal on Selected Areas in Communications，2015，33(1)：55-66.

作者信息：

李小文，李新梅，王曉娟

（重慶郵電大學 移動通信重慶市重點實驗室，重慶400065）