0 引言

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

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

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

1 發(fā)現(xiàn)過程及其模型

    為了方便標識設(shè)備中各個應(yīng)用程序，本文采用應(yīng)用程序名稱對應(yīng)的ASCII值的總和作為其標識值。因為各個應(yīng)用程序的名稱不相同，所以標識值可以唯一標識各個應(yīng)用程序。統(tǒng)計當下設(shè)備中各個應(yīng)用程序的名稱，發(fā)現(xiàn)所占字節(jié)數(shù)如圖1所示。

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

    實際上，發(fā)現(xiàn)消息就是經(jīng)過RLE編碼之后的分頁集合G_p的標識之一。

2 發(fā)現(xiàn)消息設(shè)計

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

2.1 發(fā)現(xiàn)消息二叉樹的構(gòu)造

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

    基于上述過程，設(shè)備可以通過算法1為特定G_p構(gòu)造一顆二叉樹。

    算法1：

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

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

    (3)若較?。ù螅┓秶鷥H包含作業(yè)應(yīng)用程序標識，則不進行下一步劃分。一個葉節(jié)點和一個邊緣被添加到當前節(jié)點的左（右）側(cè)；

    (4)若較?。ù螅┓秶鷥H包含非作業(yè)的應(yīng)用程序標識值，則不進行下一步劃分。在當前節(jié)點的左（右）側(cè)不添加節(jié)點；

    (5)若較?。ù螅┓秶瑑煞N不同的應(yīng)用程序標識值，那么進行下一步的劃分。在當前節(jié)點的左（右）側(cè)添加一個節(jié)點和一個邊緣，并且將搜索范圍改為[x，(x+y)/2]和([(x+y)/2，y])，進行步驟(2)的操作；

    (6)若沒有范圍進一步劃分，那么發(fā)現(xiàn)消息二叉樹構(gòu)造完成，否則，轉(zhuǎn)到步驟(2)。

2.2 發(fā)現(xiàn)消息的構(gòu)造

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

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

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

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

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

    (4)葉節(jié)點本身。

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

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

    算法2：

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

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

    ①若相等，計數(shù)器加1，位置指針加1，直到不相等的數(shù)值出現(xiàn)，按照計數(shù)值在前數(shù)值在后的規(guī)則，進行發(fā)現(xiàn)消息的構(gòu)造,進行步驟(3)；

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

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

    (4)結(jié)束程序，完成發(fā)現(xiàn)消息的構(gòu)造。

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

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

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

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

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

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

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

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

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

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

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

    ②否則，退出程序；

    (8)結(jié)束程序。

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

3 性能分析

    發(fā)現(xiàn)消息的理想設(shè)計是通過最短的消息發(fā)現(xiàn)大量的設(shè)備，并且不會出現(xiàn)錯誤率?；谏鲜龇治?，所提出的發(fā)現(xiàn)消息可以精確指示多個應(yīng)用程序。此外，本文所提出的設(shè)計性能取決于設(shè)備中作業(yè)和非作業(yè)應(yīng)用程序的數(shù)量。

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

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

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

    由表2可得發(fā)現(xiàn)二叉樹的節(jié)點統(tǒng)計期望：

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

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

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

    在本文中，某一位置出現(xiàn)0的概率為：

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

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

4 結(jié)論

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

參考文獻

[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] 董自強，劉燦燦.基于鄰近服務(wù)的D2D節(jié)點發(fā)現(xiàn)技術(shù)綜述[J].微型機與應(yīng)用，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].微型機與應(yīng)用，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.

作者信息：

李小文，李新梅，王曉娟

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