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)用程序的標(biāo)識值范圍而不是標(biāo)識值來減少發(fā)現(xiàn)消息的大小，隨后通過使用二叉樹^[5-6]來表示分頁的范圍,，并通過RLE編碼^[5]的二叉樹的比特信息來通知作業(yè)設(shè)備應(yīng)用程序的值范圍,，以此實現(xiàn)高效無誤的設(shè)備對發(fā)現(xiàn)過程。

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

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

    從普遍性的角度，可用72個比特來標(biāo)識各個應(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)用程序標(biāo)識值的最大值為M,，M=2⁷²，那么作業(yè)應(yīng)用程序的分頁范圍的最大長度就為M,，最小長度為1,。特定發(fā)現(xiàn)周期中的所有分頁范圍構(gòu)成分頁集合Gp，其互補集合就是未分頁區(qū)域的值范圍,。

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

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)用程序標(biāo)識值唯一地創(chuàng)建發(fā)現(xiàn)消息二叉樹,。當(dāng)通過二叉樹表示分頁范圍時，迭代中點細分法用于將整個值范圍[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，將當(dāng)前節(jié)點設(shè)置為根節(jié)點,；

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

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

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

    (5)若較?。ù螅┓秶瑑煞N不同的應(yīng)用程序標(biāo)識值，那么進行下一步的劃分,。在當(dā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)先的遍歷準(zhǔn)則，按順序輸出每個節(jié)點的兩位以形成二進制比特串,，隨后通過算法2使用的RLE編碼將比特串編碼為最終的發(fā)現(xiàn)消息,。

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

    算法2：

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

    (2)對比循環(huán)讀取的值與當(dāng)前要進行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)先準(zhǔn)則,，將比特串轉(zhuǎn)化為一棵二叉樹，隨后判斷設(shè)備中的應(yīng)用程序標(biāo)識值是否屬于由該二叉樹表示的集合,，僅當(dāng)其標(biāo)識值屬于該集合時,，才可認為含有此應(yīng)用程序的終端就是目標(biāo)設(shè)備，具體的判斷方法如下：

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

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

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

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

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

    (6)如果當(dāng)前判斷的標(biāo)識值>mid,；

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

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

    (7)如果判斷的標(biāo)識值<mid,；

    ①若當(dāng)前節(jié)點的左子樹存在，設(shè)置end=mid,，將該節(jié)點的左子樹的根節(jié)點為當(dāng)前判斷節(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)用程序標(biāo)識值的不同分布而變化的,，因此期望函數(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)計標(biāo)準(zhǔn)中的發(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)用程序的標(biāo)識范圍,，這要比傳統(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）