董自強(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)的典型解決方案和研究成果,。
　　關(guān)鍵詞： D2D；節(jié)點(diǎn)發(fā)現(xiàn),；傳感網(wǎng)　　

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è)備已更新的成員列表,。
　　

　　對(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搜索,。
　　

　　CQuest由三個(gè)部分組成。
　?。?）每個(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é)議。
　?。?）維持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é)了一些有代表性的解決方案，最后,，列舉了一些熱門的開放性問題,。
　　參考文獻(xiàn)
　　［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.
　?。?］ 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.
　?。?］ 陳良銀, 顏秉姝, 張靖宇, 等. 移動(dòng)低占空比傳感網(wǎng)鄰居發(fā)現(xiàn)算法［J］. 軟件學(xué)報(bào), 2014, 25(6): 13521368.
　　［4］ PITKNEN M, KRKKINEN T, OTT J. Mobility and service discovery in opportunistic networks［C］.2012 IEEE International Conference on Pervasive Computing and Communications Workshops (PERCOM Workshops), IEEE, 2012: 204210.
　?。?］ KRAVETS R H. Enabling social interactions off the grid［J］. Pervasive Computing, IEEE, 2012, 11(2): 811.
　?。?］ 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.
　?。?］ 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.
　?。?］ 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.
　?。?1］ 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.
　?。?2］ CAMPSMUR D, GARCIASAAVEDRA A, SERRANO P. Devicetodevice communications with WiFi direct: overview and experimentation［J］. Wireless Communications, IEEE, 2013,