0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    (4)葉節(jié)點(diǎn)本身。

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

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

    算法2：

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    ②否則，退出程序；

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

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

3 性能分析

    發(fā)現(xiàn)消息的理想設(shè)計(jì)是通過最短的消息發(fā)現(xiàn)大量的設(shè)備，并且不會(huì)出現(xiàn)錯(cuò)誤率。基于上述分析，所提出的發(fā)現(xiàn)消息可以精確指示多個(gè)應(yīng)用程序。此外，本文所提出的設(shè)計(jì)性能取決于設(shè)備中作業(yè)和非作業(yè)應(yīng)用程序的數(shù)量。

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

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

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

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

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

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

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

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

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

    發(fā)現(xiàn)消息的大小是實(shí)現(xiàn)高效D2D通信的關(guān)鍵問題之一^[7]，因此本文通過研究發(fā)現(xiàn)消息大小的方式來(lái)評(píng)估所提方法的性能。圖2顯示了所提方案在不同作業(yè)應(yīng)用程序下的累積分布圖，由該圖可得在90%的仿真結(jié)果中，所提方案可以在較小比特長(zhǎng)度的情況下，能夠很好地發(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種方案對(duì)于發(fā)現(xiàn)消息減少方法都實(shí)現(xiàn)了顯著的增強(qiáng)。而且所提方案相比于bloom方案存在的假肯定性錯(cuò)誤和比特個(gè)數(shù)而言，它的效果顯然是更優(yōu)的。并且本文所提方案在二叉樹的基礎(chǔ)上又進(jìn)行了一次RLE編碼，更好地實(shí)現(xiàn)了縮短發(fā)現(xiàn)消息大小的目的。

4 結(jié)論

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

參考文獻(xiàn)

[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] 董自強(qiáng)，劉燦燦.基于鄰近服務(wù)的D2D節(jié)點(diǎn)發(fā)現(xiàn)技術(shù)綜述[J].微型機(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] 周愛武，吳國(guó)進(jìn)，崔丹丹.一種改進(jìn)的二叉樹多分支持向量機(jī)算法[J].微型機(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é) 移動(dòng)通信重慶市重點(diǎn)實(shí)驗(yàn)室，重慶400065）