0 引言

作為5G通信的關(guān)鍵候選技術(shù)之一[1]，D2D通信技術(shù)可以實(shí)現(xiàn)基于鄰近服務(wù)設(shè)備之間的直接通信要求，具有降低服務(wù)基站負(fù)荷的優(yōu)勢(shì)。D2D發(fā)現(xiàn)過(guò)程作為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)過(guò)程所使用的發(fā)現(xiàn)消息是基于應(yīng)用程序名稱設(shè)計(jì)的，這樣不僅使得內(nèi)存方面不能滿足日益增長(zhǎng)的數(shù)據(jù)要求，而且也使得數(shù)據(jù)傳輸速率方面有所欠缺。

因此，對(duì)此問(wèn)題的相關(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過(guò)濾器數(shù)據(jù)結(jié)構(gòu)和K個(gè)hash函數(shù)來(lái)設(shè)計(jì)。由文獻(xiàn)[3]、[4]所述，在應(yīng)用程序發(fā)現(xiàn)的過(guò)程中，假肯定情況是不可避免的，而且，降低錯(cuò)誤的概率則會(huì)顯著增加發(fā)現(xiàn)信息的大小。

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

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

為了方便標(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=272，那么作業(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)過(guò)RLE編碼之后的分頁(yè)集合Gp的標(biāo)識(shí)之一。

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

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

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

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

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

算法1：

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

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

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

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

(5)若較小（大）范圍包含兩種不同的應(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)若沒(méi)有范圍進(jìn)一步劃分，那么發(fā)現(xiàn)消息二叉樹(shù)構(gòu)造完成，否則，轉(zhuǎn)到步驟(2)。

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

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

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

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

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

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

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

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

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

算法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è)備通過(guò)RLE進(jìn)行比特串的解碼，然后按照寬度優(yōu)先準(zhǔn)則，將比特串轉(zhuǎn)化為一棵二叉樹(shù)，隨后判斷設(shè)備中的應(yīng)用程序標(biāo)識(shí)值是否屬于由該二叉樹(shù)表示的集合，僅當(dāng)其標(biāo)識(shí)值屬于該集合時(shí)，才可認(rèn)為含有此應(yīng)用程序的終端就是目標(biāo)設(shè)備，具體的判斷方法如下：

(1)首先，接收到經(jīng)過(guò)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è)的，退出判斷過(guò)程。否則，設(shè)置中點(diǎn)為mid=(Start+end)/2；

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

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

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

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

①若當(dāng)前節(jié)點(diǎn)的左子樹(shù)存在，設(shè)置end=mid，將該節(jié)點(diǎn)的左子樹(shù)的根節(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ì)是通過(guò)最短的消息發(fā)現(xiàn)大量的設(shè)備，并且不會(huì)出現(xiàn)錯(cuò)誤率。基于上述分析，所提出的發(fā)現(xiàn)消息可以精確指示多個(gè)應(yīng)用程序。此外，本文所提出的設(shè)計(jì)性能取決于設(shè)備中作業(yè)和非作業(yè)應(yīng)用程序的數(shù)量。

由于分頁(yè)二叉樹(shù)上的每個(gè)節(jié)點(diǎn)由兩個(gè)比特表示，因此首先分析的是二叉樹(shù)上的節(jié)點(diǎn)的期望數(shù)量。假設(shè)在[0，M-1]分布范圍內(nèi)有L個(gè)應(yīng)用程序，由于發(fā)現(xiàn)消息二叉樹(shù)是基于應(yīng)用程序標(biāo)識(shí)值的不同分布而變化的，因此期望函數(shù)E(M，n，m)被定義為發(fā)現(xiàn)二叉樹(shù)中的期望節(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)造的特定二叉樹(shù)的概率被定義為P(M，n，m，i，j)，含義：在該特定二叉樹(shù)中，由根節(jié)點(diǎn)的左子樹(shù)表示的范圍包含i個(gè)作業(yè)和j個(gè)非作業(yè)應(yīng)用程序，而由右子樹(shù)表示的范圍內(nèi)包含n-i個(gè)作業(yè)和m-j個(gè)非作業(yè)應(yīng)用程序。表2給出了不同特定二叉樹(shù)的節(jié)點(diǎn)數(shù)和其概率。

那么，二叉樹(shù)中的總節(jié)點(diǎn)數(shù)分為一個(gè)根節(jié)點(diǎn)和左、右子樹(shù)中節(jié)點(diǎn)數(shù)的總數(shù)。左子樹(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)二叉樹(shù)的節(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ù)量最大的概率為：

假定消息二叉樹(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)的概率為pl(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)鍵問(wèn)題之一[7]，因此本文通過(guò)研究發(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)的。并且本文所提方案在二叉樹(shù)的基礎(chǔ)上又進(jìn)行了一次RLE編碼，更好地實(shí)現(xiàn)了縮短發(fā)現(xiàn)消息大小的目的。

4 結(jié)論

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