董自強(qiáng)，劉燦燦
　?。暇┼]電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210000）

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

0引言
　　最近幾年D2D(devicetodevice)技術(shù)相當(dāng)流行，它是新一代通信模式，能讓移動(dòng)終端與其他終端不需要透過(guò)網(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)鍵問(wèn)題之一。
　　目前已經(jīng)有很多基于鄰近服務(wù)的D2D節(jié)點(diǎn)發(fā)現(xiàn)技術(shù)，大體可分為有外部架構(gòu)輔助和無(wú)外部架構(gòu)輔助兩類［1］。本文重點(diǎn)說(shuō)明沒(méi)有外部架構(gòu)輔助的直接節(jié)點(diǎn)搜索的情況。
　　沒(méi)有外部架構(gòu)輔助的D2D節(jié)點(diǎn)的搜索就不需要基站的參與，這樣節(jié)點(diǎn)的搜索就可以控制在局部范圍進(jìn)行操作，而且搜索過(guò)程的復(fù)雜性也被轉(zhuǎn)移到用戶終端，所以這種方法更靈活而且伸縮性強(qiáng)。另外，在沒(méi)有蜂窩網(wǎng)絡(luò)覆蓋的情況下（意味著沒(méi)有外部架構(gòu)輔助），必須選擇這類沒(méi)有架構(gòu)輔助的搜索方案。然而，如果沒(méi)有外部架構(gòu)的輔助，也就意味著在沒(méi)有網(wǎng)絡(luò)協(xié)調(diào)的情況下，D2D設(shè)備必須在節(jié)點(diǎn)搜索的過(guò)程中盲目地解碼搜索信號(hào)：D2D設(shè)備需要一直發(fā)送搜尋信標(biāo)，對(duì)移動(dòng)設(shè)備來(lái)說(shuō)這是非常耗時(shí)和耗能的。在搜索的過(guò)程中還有一些其他的挑戰(zhàn)，因此本文將詳細(xì)描述如何解決節(jié)點(diǎn)發(fā)現(xiàn)過(guò)程中的主要問(wè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)。研究表明:在搜索過(guò)程中，D2D節(jié)點(diǎn)的絕大部分能量消耗在空閑偵聽(tīng)(Idle Listening,即節(jié)點(diǎn)等待接收信息)階段。而減少空閑偵聽(tīng)的主要技術(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ú)線傳感器網(wǎng)絡(luò)中,由于節(jié)點(diǎn)長(zhǎng)時(shí)間處于休眠狀態(tài)(比如99%的時(shí)間休眠)［3］,且節(jié)點(diǎn)間有可能異步,因此,在沒(méi)有任何輔助設(shè)施(比如沒(méi)有定向天線、沒(méi)有同步、沒(méi)有基站、沒(méi)有GPS 等)的情況下，兩個(gè)物理鄰居節(jié)點(diǎn)很難同時(shí)處于蘇醒狀態(tài)并相互發(fā)現(xiàn)。此外D2D節(jié)點(diǎn)具有移動(dòng)性等因素也使節(jié)點(diǎn)發(fā)現(xiàn)問(wèn)題將變得更加困難。
　　基于以上所述，在沒(méi)有外部架構(gòu)的輔助的情況下，設(shè)計(jì)出合理的節(jié)點(diǎn)發(fā)現(xiàn)方案顯得非常重要。本文主要關(guān)注兩種近距離網(wǎng)絡(luò)傳輸技術(shù)：WiFi和藍(lán)牙［4］。
　　本文介紹了在沒(méi)有外部設(shè)備輔助情況下D2D節(jié)點(diǎn)的發(fā)現(xiàn)所面臨的主要挑戰(zhàn),描述了一些能夠解決這些挑戰(zhàn)的一些典型方案，列舉了一些熱門的開(kāi)放性問(wèn)題。
2挑戰(zhàn)及概念介紹
　　2.1主要挑戰(zhàn)
　　沒(méi)有外部架構(gòu)的輔助，節(jié)點(diǎn)的搜索就可以控制在局部范圍進(jìn)行操作，這使得搜索過(guò)程更靈活，然而，搜索過(guò)程的復(fù)雜性也被轉(zhuǎn)移到用戶終端。無(wú)外部架構(gòu)輔助的節(jié)點(diǎn)搜索面臨的主要挑戰(zhàn)是能源效率、快速發(fā)現(xiàn)、異步搜索和可伸縮性。
　　如果沒(méi)有能耗的限制，節(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。在沒(méi)有其他架構(gòu)輔助的情況下，通常設(shè)備A會(huì)周期性地發(fā)送信標(biāo)信號(hào)以便讓其他設(shè)備能發(fā)現(xiàn)它，所以設(shè)備B可以通過(guò)簡(jiǎn)單的掃描信標(biāo)信號(hào)來(lái)發(fā)現(xiàn)A［5］。然而，某種程度上來(lái)說(shuō)，設(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í)間里讓無(wú)線接口保持在休眠狀態(tài)中，并定期將其喚醒以執(zhí)行搜索任務(wù)。當(dāng)然，兩個(gè)互相搜索的設(shè)備要想發(fā)現(xiàn)對(duì)方必須保持喚醒狀態(tài)，所以應(yīng)該制定合適的占空比方案來(lái)確保兩個(gè)鄰近設(shè)備的喚醒時(shí)間是重疊的。通過(guò)時(shí)間的同步可以讓設(shè)備同時(shí)處于喚醒狀態(tài)，而且這并不難實(shí)現(xiàn)。然而，同步需要基礎(chǔ)設(shè)施的支持（4G /無(wú)線基站），或使用車載GPS組件，但不能一直使用，因?yàn)槟芎木薮?。因此，在無(wú)法獲得同步時(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概念介紹
　　本文接下來(lái)將介紹幾種可以有效解決上述難題的節(jié)點(diǎn)搜索方案。首先需要說(shuō)明節(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)從開(kāi)始搜索到完成搜索所經(jīng)過(guò)的時(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)搜索過(guò)程中時(shí)隙序列相同的調(diào)度，也就是具有相同占空比被稱為對(duì)稱。
　　(7)非對(duì)稱性：節(jié)點(diǎn)搜索過(guò)程中時(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）（參見(jiàn)圖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重疊的可能性大大增加。在順序探照燈方案中（參見(jiàn)圖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è)主要問(wèn)題。首先，分散的設(shè)備如何能夠組成一個(gè)按序發(fā)送信標(biāo)的群組？其次，設(shè)備是移動(dòng)的，如何在移動(dòng)的環(huán)境中維持這個(gè)群組？第三，形成一個(gè)群組會(huì)引進(jìn)額外的能耗，這是否會(huì)使弊大于利？
　　對(duì)于第一個(gè)問(wèn)題，該方案被分為兩個(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è)問(wèn)題，該方案引入了增強(qiáng)技術(shù)。在移動(dòng)環(huán)境中，成員設(shè)備可能頻繁地移動(dòng)出群組通信范圍。因此，群組可能經(jīng)常重組，這會(huì)導(dǎo)致程序崩潰，而且這也不符合能源效率和可擴(kuò)展性的要求。如圖2所示，增強(qiáng)技術(shù)就是假設(shè)A沒(méi)有收到B的ACK消息（B的更新窗發(fā)送），A將另外發(fā)送一個(gè)信標(biāo)給C，從而降低群組斷鏈重組的頻率。
　　對(duì)于第三個(gè)問(wèn)題，該方案只需要設(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è)集群成員可以通過(guò)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)下一輪開(kāi)始掃描。這顯然會(huì)產(chǎn)生競(jìng)爭(zhēng)，CQuest提供了詳細(xì)的解決方案，這里不再闡述。
　?。?）關(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è)閾值來(lái)確定是否有成員離開(kāi)集群。
4開(kāi)放性研究問(wèn)題
　　在D2D節(jié)點(diǎn)發(fā)現(xiàn)的過(guò)程中，依舊存在著一些研究問(wèn)題。
　　4.1網(wǎng)絡(luò)輔助和定位
　　利用定位技術(shù)和網(wǎng)絡(luò)云的輔助，可以有效提高節(jié)點(diǎn)搜索效率，例如網(wǎng)絡(luò)服務(wù)器可根據(jù)節(jié)點(diǎn)所在位置分析出周圍是否存在可搜索節(jié)點(diǎn)，若沒(méi)有，則關(guān)閉節(jié)點(diǎn)搜索開(kāi)關(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)搜索中的主要問(wèn)題，針對(duì)這些問(wèn)題總　　結(jié)了一些有代表性的解決方案，最后，列舉了一些熱門的開(kāi)放性問(wèn)題。
　　參考文獻(xiàn)
　?。?］ 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.
　　［5］ 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.
　?。?］ 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.
　?。?0］ 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.
　?。?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,