基于鄰近服務(wù)的D2D節(jié)點(diǎn)發(fā)現(xiàn)技術(shù)綜述

董自強(qiáng)，劉燦燦

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210000)

?

基于鄰近服務(wù)的D2D節(jié)點(diǎn)發(fā)現(xiàn)技術(shù)綜述

董自強(qiáng)，劉燦燦

(南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210000)

D2D節(jié)點(diǎn)發(fā)現(xiàn)技術(shù)是實(shí)現(xiàn)D2D通信首先要解決的重要問題。圍繞無架構(gòu)輔助的D2D節(jié)點(diǎn)搜索問題，對(duì)其研究現(xiàn)狀進(jìn)行了系統(tǒng)的梳理和述評(píng)，指出了該領(lǐng)域現(xiàn)有研究存在的問題，并綜述了相應(yīng)的典型解決方案和研究成果。

D2D；節(jié)點(diǎn)發(fā)現(xiàn)；傳感網(wǎng)

引用格式：董自強(qiáng)，劉燦燦. 基于鄰近服務(wù)的D2D節(jié)點(diǎn)發(fā)現(xiàn)技術(shù)綜述[J].微型機(jī)與應(yīng)用，2016,35(16)：60-62，66.

0　引言

最近幾年D2D(device-to-device)技術(shù)相當(dāng)流行，它是新一代通信模式，能讓移動(dòng)終端與其他終端不需要透過網(wǎng)絡(luò)傳遞就可實(shí)現(xiàn)相互之間的通信。但是在D2D節(jié)點(diǎn)(設(shè)備)建立連接之前，設(shè)備必須先發(fā)現(xiàn)其他D2D節(jié)點(diǎn)。節(jié)點(diǎn)發(fā)現(xiàn)是進(jìn)行D2D通信的基礎(chǔ)，因此也是D2D通信的關(guān)鍵問題之一。

目前已經(jīng)有很多基于鄰近服務(wù)的D2D節(jié)點(diǎn)發(fā)現(xiàn)技術(shù)，大體可分為有外部架構(gòu)輔助和無外部架構(gòu)輔助兩類[1]。本文重點(diǎn)說明沒有外部架構(gòu)輔助的直接節(jié)點(diǎn)搜索的情況。

沒有外部架構(gòu)輔助的D2D節(jié)點(diǎn)的搜索就不需要基站的參與，這樣節(jié)點(diǎn)的搜索就可以控制在局部范圍進(jìn)行操作，而且搜索過程的復(fù)雜性也被轉(zhuǎn)移到用戶終端，所以這種方法更靈活而且伸縮性強(qiáng)。另外，在沒有蜂窩網(wǎng)絡(luò)覆蓋的情況下(意味著沒有外部架構(gòu)輔助)，必須選擇這類沒有架構(gòu)輔助的搜索方案。然而，如果沒有外部架構(gòu)的輔助，也就意味著在沒有網(wǎng)絡(luò)協(xié)調(diào)的情況下，D2D設(shè)備必須在節(jié)點(diǎn)搜索的過程中盲目地解碼搜索信號(hào)：D2D設(shè)備需要一直發(fā)送搜尋信標(biāo)，對(duì)移動(dòng)設(shè)備來說這是非常耗時(shí)和耗能的。在搜索的過程中還有一些其他的挑戰(zhàn)，因此本文將詳細(xì)描述如何解決節(jié)點(diǎn)發(fā)現(xiàn)過程中的主要問題。

1　概述

D2D技術(shù)是新一代通信領(lǐng)域的研究熱點(diǎn)之一，D2D節(jié)點(diǎn)搜索是這項(xiàng)技術(shù)首先要解決的難點(diǎn)之一，也是這項(xiàng)技術(shù)實(shí)現(xiàn)的重點(diǎn)。研究表明:在搜索過程中，D2D節(jié)點(diǎn)的絕大部分能量消耗在空閑偵聽(Idle Listening,即節(jié)點(diǎn)等待接收信息)階段。而減少空閑偵聽的主要技術(shù)就是占空比(Duty Cycle)技術(shù),即讓節(jié)點(diǎn)交替處于工作和休眠狀態(tài),從而節(jié)省節(jié)點(diǎn)能量。低占空比(Low Duty Cycle,LDC)[2]技術(shù)則讓節(jié)點(diǎn)絕大部分時(shí)間處于休眠狀態(tài),極少時(shí)間處于工作狀態(tài)(比如節(jié)點(diǎn)1%的時(shí)間處于工作狀態(tài)即蘇醒狀態(tài),其余99%的時(shí)間處于休眠狀態(tài))。在低占空比無線傳感器網(wǎng)絡(luò)中,由于節(jié)點(diǎn)長(zhǎng)時(shí)間處于休眠狀態(tài)(比如99%的時(shí)間休眠)[3],且節(jié)點(diǎn)間有可能異步,因此,在沒有任何輔助設(shè)施(比如沒有定向天線、沒有同步、沒有基站、沒有GPS 等)的情況下，兩個(gè)物理鄰居節(jié)點(diǎn)很難同時(shí)處于蘇醒狀態(tài)并相互發(fā)現(xiàn)。此外D2D節(jié)點(diǎn)具有移動(dòng)性等因素也使節(jié)點(diǎn)發(fā)現(xiàn)問題將變得更加困難。

基于以上所述，在沒有外部架構(gòu)的輔助的情況下，設(shè)計(jì)出合理的節(jié)點(diǎn)發(fā)現(xiàn)方案顯得非常重要。本文主要關(guān)注兩種近距離網(wǎng)絡(luò)傳輸技術(shù)：WiFi和藍(lán)牙[4]。

本文介紹了在沒有外部設(shè)備輔助情況下D2D節(jié)點(diǎn)的發(fā)現(xiàn)所面臨的主要挑戰(zhàn),描述了一些能夠解決這些挑戰(zhàn)的一些典型方案，列舉了一些熱門的開放性問題。

2　挑戰(zhàn)及概念介紹

2.1主要挑戰(zhàn)

沒有外部架構(gòu)的輔助，節(jié)點(diǎn)的搜索就可以控制在局部范圍進(jìn)行操作，這使得搜索過程更靈活，然而，搜索過程的復(fù)雜性也被轉(zhuǎn)移到用戶終端。無外部架構(gòu)輔助的節(jié)點(diǎn)搜索面臨的主要挑戰(zhàn)是能源效率、快速發(fā)現(xiàn)、異步搜索和可伸縮性。

如果沒有能耗的限制，節(jié)點(diǎn)發(fā)現(xiàn)就簡(jiǎn)單多了，可以讓每臺(tái)設(shè)備周期性地發(fā)送信標(biāo)以便其他設(shè)備能及時(shí)快速地發(fā)現(xiàn)它的存在。例如，假設(shè)有設(shè)備A和設(shè)備B，設(shè)備B想發(fā)現(xiàn)設(shè)備A。在沒有其他架構(gòu)輔助的情況下，通常設(shè)備A會(huì)周期性地發(fā)送信標(biāo)信號(hào)以便讓其他設(shè)備能發(fā)現(xiàn)它，所以設(shè)備B可以通過簡(jiǎn)單的掃描信標(biāo)信號(hào)來發(fā)現(xiàn)A[5]。然而，某種程度上來說，設(shè)備的能源效率和快速發(fā)現(xiàn)是一對(duì)矛盾。為了實(shí)現(xiàn)節(jié)點(diǎn)的快速發(fā)現(xiàn)，設(shè)備A需要發(fā)送的信標(biāo)周期較短，這意味著消耗更多的能量，因此設(shè)備的能源效率和快速發(fā)現(xiàn)相互之間存在一個(gè)折衷。

相反，設(shè)備可以按照一定比例的占空比，在大部分時(shí)間里讓無線接口保持在休眠狀態(tài)中，并定期將其喚醒以執(zhí)行搜索任務(wù)。當(dāng)然，兩個(gè)互相搜索的設(shè)備要想發(fā)現(xiàn)對(duì)方必須保持喚醒狀態(tài)，所以應(yīng)該制定合適的占空比方案來確保兩個(gè)鄰近設(shè)備的喚醒時(shí)間是重疊的。通過時(shí)間的同步可以讓設(shè)備同時(shí)處于喚醒狀態(tài)，而且這并不難實(shí)現(xiàn)。然而，同步需要基礎(chǔ)設(shè)施的支持(4G /無線基站)，或使用車載GPS組件，但不能一直使用，因?yàn)槟芎木薮?。因此，在無法獲得同步時(shí)鐘且保證低占空比的情況下，為了確保鄰近設(shè)備的喚醒時(shí)間在合理的時(shí)間內(nèi)重疊，不少研究人員提出了異步搜索方案。

可伸縮性：節(jié)點(diǎn)搜索協(xié)議應(yīng)當(dāng)能在高度密集的環(huán)境中正常工作。如果希望許多設(shè)備能同時(shí)被搜索到，那么所有設(shè)備將在同一時(shí)間內(nèi)一同發(fā)送信標(biāo)，這些信標(biāo)信號(hào)的傳輸有可能導(dǎo)致信號(hào)流量擁塞，從而使一些設(shè)備不能發(fā)現(xiàn)。

2.2概念介紹

本文接下來將介紹幾種可以有效解決上述難題的節(jié)點(diǎn)搜索方案。首先需要說明節(jié)點(diǎn)搜索方案中常用的概念，包括：時(shí)隙、搜索周期、搜索延遲、最長(zhǎng)搜索延遲、占空比、對(duì)稱性和非對(duì)稱性。

(1)時(shí)隙：時(shí)間被分成具有相同大小的間隔，每個(gè)時(shí)間間隔被稱為一個(gè)時(shí)隙。時(shí)隙的概念可以減少相關(guān)實(shí)驗(yàn)的困難，當(dāng)確保該時(shí)隙的長(zhǎng)度大于總時(shí)鐘偏移，就可以有效地克服時(shí)鐘的偏移的影響。

(2)搜索周期：N個(gè)時(shí)隙組成一個(gè)搜索周期。在一個(gè)搜索周期內(nèi)，按照某個(gè)時(shí)間表安排節(jié)點(diǎn)的工作狀態(tài)。

(3)搜索延遲：在彼此的通信范圍內(nèi)，兩個(gè)節(jié)點(diǎn)從開始搜索到完成搜索所經(jīng)過的時(shí)間長(zhǎng)度。

(4)最長(zhǎng)搜索延遲：一個(gè)節(jié)點(diǎn)發(fā)現(xiàn)它所有鄰居的最長(zhǎng)延遲。它表示兩個(gè)節(jié)點(diǎn)在其通信范圍內(nèi)確?？梢园l(fā)現(xiàn)彼此所需要的最小時(shí)長(zhǎng)。

(5)占空比：節(jié)點(diǎn)從工作或睡眠狀態(tài)定期交替。一個(gè)節(jié)點(diǎn)的工作狀態(tài)的持續(xù)時(shí)間與總時(shí)間長(zhǎng)度的比值稱為占空比。

(6)對(duì)稱性：節(jié)點(diǎn)搜索過程中時(shí)隙序列相同的調(diào)度，也就是具有相同占空比被稱為對(duì)稱。

(7)非對(duì)稱性：節(jié)點(diǎn)搜索過程中時(shí)隙序列不同的調(diào)度，也就是具有不同占空比被稱為非對(duì)稱[6]。

3　解決方案

根據(jù)以上提出的挑戰(zhàn)，對(duì)有關(guān)節(jié)點(diǎn)搜索方面的一些研究文獻(xiàn)總結(jié)如下。

3.1探照燈方案

節(jié)能的異步節(jié)點(diǎn)搜索方案可以分兩類：概率性方案和確定性方案，它們各有優(yōu)缺點(diǎn)。探照燈方案[7]結(jié)合了這兩種方案，在設(shè)備的能源效率和快速發(fā)現(xiàn)之間保持了平衡。具體而言，探照燈利用基于時(shí)隙的周期性搜索表，一個(gè)周期包含t個(gè)時(shí)隙，為了節(jié)約能源，設(shè)備在大多數(shù)時(shí)隙處于休眠狀態(tài)。

每個(gè)周期有兩個(gè)活動(dòng)時(shí)隙：錨時(shí)隙(A)和探測(cè)時(shí)隙(P)(參見圖1，t=7)。能成功搜索到鄰近節(jié)點(diǎn)的情況有3種：AA重疊、PA重疊和PP重疊。一般情況下，不會(huì)發(fā)生AA重疊，因?yàn)閠足夠大(為了簡(jiǎn)化，圖1中t取值較小)，所以這里只討論另外兩種情況。

錨時(shí)隙的位置固定在每個(gè)周期的第一個(gè)時(shí)隙。如果兩個(gè)節(jié)點(diǎn)的周期相同，則兩個(gè)節(jié)點(diǎn)錨時(shí)隙的相對(duì)位置保持不變，如圖1所示，節(jié)點(diǎn)B的錨時(shí)隙相對(duì)于節(jié)點(diǎn)A總是延后4個(gè)時(shí)隙。

這種搜索法案的好處是節(jié)點(diǎn)只需要探測(cè)半個(gè)周期的時(shí)隙，如圖1所示，P時(shí)隙只要按照1, 2, 3，…，t/2的模式就能確保PA重疊情況的出現(xiàn)。

此外，如圖1(b)所示，P時(shí)隙不按照順序出現(xiàn)的方案叫做隨機(jī)探照燈，這種方案使PP重疊的可能性大大增加。在順序探照燈方案中(參見圖1(a))，兩個(gè)節(jié)點(diǎn)的P時(shí)隙遵循相同的模式，因此它們經(jīng)常保持同步，大大減少了PP重疊的發(fā)生概率。隨機(jī)探照燈參照了概率性的思想，在這種方案中，P時(shí)隙可以隨機(jī)地選擇不同模式，實(shí)現(xiàn)了概率性和確定性方法的結(jié)合，比如圖1(b)中，節(jié)點(diǎn)A每個(gè)周期中P時(shí)隙距離A時(shí)隙延遲順序?yàn)?21，節(jié)點(diǎn)B順序?yàn)?12，顯然P時(shí)隙模式不同。

3.2群組搜索方案

群組搜索方案[8]就是將鄰近區(qū)域的設(shè)備組成一個(gè)群組，群組中的設(shè)備輪流發(fā)布組員的存在消息。因此，設(shè)備可以降低發(fā)送消息的占空比，并且具有能源效率高和可伸縮性的優(yōu)點(diǎn)。此外，該組中的其他設(shè)備仍能保證被快速發(fā)現(xiàn)。

這個(gè)方案的設(shè)計(jì)中有3個(gè)主要問題。首先，分散的設(shè)備如何能夠組成一個(gè)按序發(fā)送信標(biāo)的群組？其次，設(shè)備是移動(dòng)的，如何在移動(dòng)的環(huán)境中維持這個(gè)群組？第三，形成一個(gè)群組會(huì)引進(jìn)額外的能耗，這是否會(huì)使弊大于利？

對(duì)于第一個(gè)問題，該方案被分為兩個(gè)部分：加入操作和群組操作。加入操作規(guī)定設(shè)備如何選擇群組以及如何被群組接受。群組操作可以調(diào)節(jié)成員列表，比如新成員設(shè)備的添加或從列表中刪除一個(gè)成員。如圖2所示，為了實(shí)現(xiàn)這兩個(gè)操作，引入了3個(gè)窗：加入窗、聯(lián)系窗和更新窗。加入窗可以發(fā)現(xiàn)其他設(shè)備，聯(lián)系窗可以進(jìn)行3次握手，更新窗可以通知其他設(shè)備已更新的成員列表。

圖2　信標(biāo)發(fā)送模式

對(duì)于第二個(gè)問題，該方案引入了增強(qiáng)技術(shù)。在移動(dòng)環(huán)境中，成員設(shè)備可能頻繁地移動(dòng)出群組通信范圍。因此，群組可能經(jīng)常重組，這會(huì)導(dǎo)致程序崩潰，而且這也不符合能源效率和可擴(kuò)展性的要求。如圖2所示，增強(qiáng)技術(shù)就是假設(shè)A沒有收到B的ACK消息(B的更新窗發(fā)送)，A將另外發(fā)送一個(gè)信標(biāo)給C，從而降低群組斷鏈重組的頻率。

對(duì)于第三個(gè)問題，該方案只需要設(shè)備保持低占空比，而且隨著群組成員數(shù)量的不斷增加，占空比將不斷降低。

3.3藍(lán)牙與WiFi搜索的融合

WiFi和藍(lán)牙技術(shù)在節(jié)點(diǎn)搜索中各有優(yōu)缺點(diǎn)。WiFi覆蓋范圍大但能耗也大，而藍(lán)牙能耗雖小但覆蓋范圍也小。為了節(jié)省能量，而又不減小設(shè)備的搜索范圍，可以采用CQuest搜索方案[9]。

移動(dòng)節(jié)點(diǎn)會(huì)形成臨時(shí)集群，如圖3(a)所示，每個(gè)集群成員可以通過WiFi搜索到距離較遠(yuǎn)的另一個(gè)集群的所有成員。因此，如圖3(b)所示，CQuest方案是讓每個(gè)集群成員采用功耗更低的藍(lán)牙搜索，而只保留其中一個(gè)成員的WiFi搜索。

圖3　節(jié)點(diǎn)集群搜索方式

CQuest由三個(gè)部分組成。

(1)每個(gè)集群只有選定的設(shè)備需要使用WiFi和藍(lán)牙掃描，其他設(shè)備只使用藍(lán)牙掃描。這個(gè)WiFi設(shè)備選擇的基本思路是：每個(gè)集群設(shè)備檢查是否有其他成員會(huì)在下一輪進(jìn)行WiFi掃描，如果有，該節(jié)點(diǎn)下一輪就不進(jìn)行WiFi掃描，否則，該節(jié)點(diǎn)下一輪開始掃描。這顯然會(huì)產(chǎn)生競(jìng)爭(zhēng)，CQuest提供了詳細(xì)的解決方案，這里不再闡述。

(2)關(guān)于每一輪掃描時(shí)間的確定，對(duì)于有架構(gòu)輔助的同步網(wǎng)絡(luò)，該方案可以使用有固定周期的信標(biāo)，一輪時(shí)間就可以定義為固定數(shù)目的周期。對(duì)于異步網(wǎng)絡(luò)，可以使用現(xiàn)有的異步鄰居發(fā)現(xiàn)協(xié)議。

(3)維持CQuest集群。每個(gè)集群成員都有一份集群成員名單列表，所以只要保持它們的列表同步。一旦有節(jié)點(diǎn)加入集群，其他成員的列表都會(huì)被更新。CQuest使用兩個(gè)閾值來確定是否有成員離開集群。

4　開放性研究問題

在D2D節(jié)點(diǎn)發(fā)現(xiàn)的過程中，依舊存在著一些研究問題。

4.1網(wǎng)絡(luò)輔助和定位

利用定位技術(shù)和網(wǎng)絡(luò)云的輔助，可以有效提高節(jié)點(diǎn)搜索效率，例如網(wǎng)絡(luò)服務(wù)器可根據(jù)節(jié)點(diǎn)所在位置分析出周圍是否存在可搜索節(jié)點(diǎn)，若沒有，則關(guān)閉節(jié)點(diǎn)搜索開關(guān)，從而提高搜索效率[10-11]。

4.2節(jié)點(diǎn)搜索與服務(wù)發(fā)現(xiàn)的結(jié)合

D2D節(jié)點(diǎn)搜索的目的是為了發(fā)現(xiàn)并傳輸服務(wù)，傳統(tǒng)的服務(wù)發(fā)現(xiàn)方法是搜索到節(jié)點(diǎn)后必須建立連接才可以獲知服務(wù)基本信息。例如，WiFi聯(lián)盟提出了WiFi Direct技術(shù)，該技術(shù)在節(jié)點(diǎn)搜索的信號(hào)中添加了服務(wù)信息，實(shí)現(xiàn)了節(jié)點(diǎn)搜索與服務(wù)發(fā)現(xiàn)的結(jié)合，使節(jié)點(diǎn)不需要建立連接就可獲得服務(wù)基本信息[12]。

5　結(jié)論

D2D節(jié)點(diǎn)發(fā)現(xiàn)是D2D通信的重要部分，雖然目前提出了不少解決方案，但是性能上還有很大的提高空間。本文闡述了D2D節(jié)點(diǎn)搜索中的主要問題，針對(duì)這些問題總結(jié)了一些有代表性的解決方案，最后，列舉了一些熱門的開放性問題。

[1] Lei Lei, Zhong Zhangdui, Lin Chuang, et al. Operator controlled device-to-device communications in LTE-advanced networks[J]. IEEE Wireless Communications, 2012, 19(3): 96-104.

[2] Gu Yu, He Tian. Data forwarding in extremely low duty-cycle sensor networks with unreliable communication links[C].Proceedings of the 5th International Conference on Embedded Networked Sensor Systems, ACM, 2007,19(7): 321-334.

[3] 陳良銀, 顏秉姝, 張靖宇, 等. 移動(dòng)低占空比傳感網(wǎng)鄰居發(fā)現(xiàn)算法[J]. 軟件學(xué)報(bào), 2014, 25(6): 1352-1368.

[5] KRAVETS R H. Enabling social interactions off the grid[J]. Pervasive Computing, IEEE, 2012, 11(2): 8-11.

[6] Shang Tao. A comparison between neighbour discovery protocols in low duty-cycled wireless sensor networks[J]. International Journal of Computer Science and Mobile Computing, 2015,4(2):265-271.

[7] BAKHT M, TROWER M, KRAVETS R. Searchlight: helping mobile devices find their neighbors[C].Proceedings of the 3rd ACM SOSP Workshop on Networking, Systems, and Applications on Mobile Handhelds, ACM, 2011,45(3):71-76.

[8] HUANG P K, QI E, PARK M, et al. Energy efficient and scalable device-to-device discovery protocol with fast discovery[C].2013 10th Annual IEEE Communications Society Conference on Sensor, Mesh and Ad Hoc Communications and Networks (SECON), IEEE, 2013: 1-9.

[9] BAKHT M, CARLSON J, LOEB A, et al. United we find: enabling mobile devices to cooperate for efficient neighbor discovery[C].Proceedings of the Twelfth Workshop on Mobile Computing Systems & Applications, ACM, 2012: 1-6.

[10] PRASAD A, KUNZ A, VELEV G, et al. Energy efficient D2D discovery for proximity services in 3GPP LTE-advanced Networks[J].IEEE Vehicular Technology Magezine,2014,9(3):40-50.

[11] PYATTAEV A, GALININA O, JOHNSSON K, et al. Network-assisted D2D over WiFi direct[C].Smart Device to Smart Device Communication, Springer International Publishing, 2014: 165-218.

[12] CAMPS-MUR D, GARCIA-SAAVEDRA A, SERRANO P. Device-to-device communications with Wi-Fi direct: overview and experimentation[J]. Wireless Communications, IEEE, 2013, 20(3): 96-104.

A survey of peer discovery in D2D based proximity service

Dong Ziqiang, Liu Cancan

(College of Communication and Information Engineering, Nanjing University of Posts and Telecommunications, Nanjing 210000, China)

D2D (device-to-device) peer discovery technology is an firstly important issue to achieve D2D communication. This paper reviewed and commented systematically for D2D peer discovery without infrastructure support, pointed out the existing problems in research of this field, and reviewed the corresponding typical solutions and research.

device-to-device; peer discovery; sensor network

TN92；TP3

A

10.19358/j.issn.1674- 7720.2016.16.018

2016-03-24)

董自強(qiáng)(1990-)，通信作者，男，碩士研究生，主要研究方向:D2D節(jié)點(diǎn)與服務(wù)的發(fā)現(xiàn)。E-mail:971820909@qq.com。

劉燦燦(1989-)，女，碩士研究生，主要研究方向：D2D節(jié)點(diǎn)與服務(wù)的發(fā)現(xiàn)。