董自強，劉燦燦
　　（南京郵電大學(xué) 通信與信息工程學(xué)院，江蘇 南京 210000）

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

0引言
　　最近幾年D2D(devicetodevice)技術(shù)相當(dāng)流行，它是新一代通信模式，能讓移動終端與其他終端不需要透過網(wǎng)絡(luò)傳遞就可實現(xiàn)相互之間的通信。但是在D2D節(jié)點（設(shè)備）建立連接之前，設(shè)備必須先發(fā)現(xiàn)其他D2D節(jié)點。節(jié)點發(fā)現(xiàn)是進(jìn)行D2D通信的基礎(chǔ)，因此也是D2D通信的關(guān)鍵問題之一。
　　目前已經(jīng)有很多基于鄰近服務(wù)的D2D節(jié)點發(fā)現(xiàn)技術(shù)，大體可分為有外部架構(gòu)輔助和無外部架構(gòu)輔助兩類［1］。本文重點說明沒有外部架構(gòu)輔助的直接節(jié)點搜索的情況。
　　沒有外部架構(gòu)輔助的D2D節(jié)點的搜索就不需要基站的參與，這樣節(jié)點的搜索就可以控制在局部范圍進(jìn)行操作，而且搜索過程的復(fù)雜性也被轉(zhuǎn)移到用戶終端，所以這種方法更靈活而且伸縮性強。另外，在沒有蜂窩網(wǎng)絡(luò)覆蓋的情況下（意味著沒有外部架構(gòu)輔助），必須選擇這類沒有架構(gòu)輔助的搜索方案。然而，如果沒有外部架構(gòu)的輔助，也就意味著在沒有網(wǎng)絡(luò)協(xié)調(diào)的情況下，D2D設(shè)備必須在節(jié)點搜索的過程中盲目地解碼搜索信號：D2D設(shè)備需要一直發(fā)送搜尋信標(biāo)，對移動設(shè)備來說這是非常耗時和耗能的。在搜索的過程中還有一些其他的挑戰(zhàn)，因此本文將詳細(xì)描述如何解決節(jié)點發(fā)現(xiàn)過程中的主要問題。
1概述
　　D2D技術(shù)是新一代通信領(lǐng)域的研究熱點之一，D2D節(jié)點搜索是這項技術(shù)首先要解決的難點之一，也是這項技術(shù)實現(xiàn)的重點。研究表明:在搜索過程中，D2D節(jié)點的絕大部分能量消耗在空閑偵聽(Idle Listening,即節(jié)點等待接收信息)階段。而減少空閑偵聽的主要技術(shù)就是占空比(Duty Cycle)技術(shù),即讓節(jié)點交替處于工作和休眠狀態(tài),從而節(jié)省節(jié)點能量。低占空比(Low Duty Cycle,LDC)［2］技術(shù)則讓節(jié)點絕大部分時間處于休眠狀態(tài),極少時間處于工作狀態(tài)(比如節(jié)點1%的時間處于工作狀態(tài)即蘇醒狀態(tài),其余99%的時間處于休眠狀態(tài))。在低占空比無線傳感器網(wǎng)絡(luò)中,由于節(jié)點長時間處于休眠狀態(tài)(比如99%的時間休眠)［3］,且節(jié)點間有可能異步,因此,在沒有任何輔助設(shè)施(比如沒有定向天線、沒有同步、沒有基站、沒有GPS 等)的情況下，兩個物理鄰居節(jié)點很難同時處于蘇醒狀態(tài)并相互發(fā)現(xiàn)。此外D2D節(jié)點具有移動性等因素也使節(jié)點發(fā)現(xiàn)問題將變得更加困難。
　　基于以上所述，在沒有外部架構(gòu)的輔助的情況下，設(shè)計出合理的節(jié)點發(fā)現(xiàn)方案顯得非常重要。本文主要關(guān)注兩種近距離網(wǎng)絡(luò)傳輸技術(shù)：WiFi和藍(lán)牙［4］。
　　本文介紹了在沒有外部設(shè)備輔助情況下D2D節(jié)點的發(fā)現(xiàn)所面臨的主要挑戰(zhàn),描述了一些能夠解決這些挑戰(zhàn)的一些典型方案，列舉了一些熱門的開放性問題。
2挑戰(zhàn)及概念介紹
　　2.1主要挑戰(zhàn)
　　沒有外部架構(gòu)的輔助，節(jié)點的搜索就可以控制在局部范圍進(jìn)行操作，這使得搜索過程更靈活，然而，搜索過程的復(fù)雜性也被轉(zhuǎn)移到用戶終端。無外部架構(gòu)輔助的節(jié)點搜索面臨的主要挑戰(zhàn)是能源效率、快速發(fā)現(xiàn)、異步搜索和可伸縮性。
　　如果沒有能耗的限制，節(jié)點發(fā)現(xiàn)就簡單多了，可以讓每臺設(shè)備周期性地發(fā)送信標(biāo)以便其他設(shè)備能及時快速地發(fā)現(xiàn)它的存在。例如，假設(shè)有設(shè)備A和設(shè)備B，設(shè)備B想發(fā)現(xiàn)設(shè)備A。在沒有其他架構(gòu)輔助的情況下，通常設(shè)備A會周期性地發(fā)送信標(biāo)信號以便讓其他設(shè)備能發(fā)現(xiàn)它，所以設(shè)備B可以通過簡單的掃描信標(biāo)信號來發(fā)現(xiàn)A［5］。然而，某種程度上來說，設(shè)備的能源效率和快速發(fā)現(xiàn)是一對矛盾。為了實現(xiàn)節(jié)點的快速發(fā)現(xiàn)，設(shè)備A需要發(fā)送的信標(biāo)周期較短，這意味著消耗更多的能量，因此設(shè)備的能源效率和快速發(fā)現(xiàn)相互之間存在一個折衷。
　　相反，設(shè)備可以按照一定比例的占空比，在大部分時間里讓無線接口保持在休眠狀態(tài)中，并定期將其喚醒以執(zhí)行搜索任務(wù)。當(dāng)然，兩個互相搜索的設(shè)備要想發(fā)現(xiàn)對方必須保持喚醒狀態(tài)，所以應(yīng)該制定合適的占空比方案來確保兩個鄰近設(shè)備的喚醒時間是重疊的。通過時間的同步可以讓設(shè)備同時處于喚醒狀態(tài)，而且這并不難實現(xiàn)。然而，同步需要基礎(chǔ)設(shè)施的支持（4G /無線基站），或使用車載GPS組件，但不能一直使用，因為能耗巨大。因此，在無法獲得同步時鐘且保證低占空比的情況下，為了確保鄰近設(shè)備的喚醒時間在合理的時間內(nèi)重疊，不少研究人員提出了異步搜索方案。
　　可伸縮性：節(jié)點搜索協(xié)議應(yīng)當(dāng)能在高度密集的環(huán)境中正常工作。如果希望許多設(shè)備能同時被搜索到，那么所有設(shè)備將在同一時間內(nèi)一同發(fā)送信標(biāo)，這些信標(biāo)信號的傳輸有可能導(dǎo)致信號流量擁塞，從而使一些設(shè)備不能發(fā)現(xiàn)。
　　2.2概念介紹
　　本文接下來將介紹幾種可以有效解決上述難題的節(jié)點搜索方案。首先需要說明節(jié)點搜索方案中常用的概念，包括：時隙、搜索周期、搜索延遲、最長搜索延遲、占空比、對稱性和非對稱性。
　　(1)時隙：時間被分成具有相同大小的間隔，每個時間間隔被稱為一個時隙。時隙的概念可以減少相關(guān)實驗的困難，當(dāng)確保該時隙的長度大于總時鐘偏移，就可以有效地克服時鐘的偏移的影響。
　　(2)搜索周期：N個時隙組成一個搜索周期。在一個搜索周期內(nèi)，按照某個時間表安排節(jié)點的工作狀態(tài)。
　　(3)搜索延遲：在彼此的通信范圍內(nèi)，兩個節(jié)點從開始搜索到完成搜索所經(jīng)過的時間長度。
　　(4)最長搜索延遲：一個節(jié)點發(fā)現(xiàn)它所有鄰居的最長延遲。它表示兩個節(jié)點在其通信范圍內(nèi)確?？梢园l(fā)現(xiàn)彼此所需要的最小時長。
　　(5)占空比：節(jié)點從工作或睡眠狀態(tài)定期交替。一個節(jié)點的工作狀態(tài)的持續(xù)時間與總時間長度的比值稱為占空比。
　　(6)對稱性：節(jié)點搜索過程中時隙序列相同的調(diào)度，也就是具有相同占空比被稱為對稱。
　　(7)非對稱性：節(jié)點搜索過程中時隙序列不同的調(diào)度，也就是具有不同占空比被稱為非對稱［6］。
3解決方案
　　根據(jù)以上提出的挑戰(zhàn)，對有關(guān)節(jié)點搜索方面的一些研究文獻(xiàn)總結(jié)如下。
　　3.1探照燈方案
　　節(jié)能的異步節(jié)點搜索方案可以分兩類：概率性方案和確定性方案，它們各有優(yōu)缺點。探照燈方案［7］結(jié)合了這兩種方案，在設(shè)備的能源效率和快速發(fā)現(xiàn)之間保持了平衡。具體而言，探照燈利用基于時隙的周期性搜索表，一個周期包含t個時隙，為了節(jié)約能源，設(shè)備在大多數(shù)時隙處于休眠狀態(tài)。
　　每個周期有兩個活動時隙：錨時隙（A）和探測時隙（P）（參見圖1，t=7）。能成功搜索到鄰近節(jié)點的情況有3種：AA重疊、PA重疊和PP重疊。一般情況下，不會發(fā)生AA重疊，因為t足夠大（為了簡化，圖1中t取值較?。赃@里只討論另外兩種情況。

　　　　錨時隙的位置固定在每個周期的第一個時隙。如果兩個節(jié)點的周期相同，則兩個節(jié)點錨時隙的相對位置保持不變，如圖1所示，節(jié)點B的錨時隙相對于節(jié)點A總是延后4個時隙。
　　這種搜索法案的好處是節(jié)點只需要探測半個周期的時隙，如圖1所示，P時隙只要按照1, 2, 3，…，t/2的模式就能確保PA重疊情況的出現(xiàn)。
　　此外，如圖1(b)所示，P時隙不按照順序出現(xiàn)的方案叫做隨機探照燈，這種方案使PP重疊的可能性大大增加。在順序探照燈方案中（參見圖1(a)），兩個節(jié)點的P時隙遵循相同的模式，因此它們經(jīng)常保持同步，大大減少了PP重疊的發(fā)生概率。隨機探照燈參照了概率性的思想，在這種方案中，P時隙可以隨機地選擇不同模式，實現(xiàn)了概率性和確定性方法的結(jié)合，比如圖1(b)中，節(jié)點A每個周期中P時隙距離A時隙延遲順序為321，節(jié)點B順序為312，顯然P時隙模式不同。
　　3.2群組搜索方案
　　群組搜索方案［8］就是將鄰近區(qū)域的設(shè)備組成一個群組，群組中的設(shè)備輪流發(fā)布組員的存在消息。因此，設(shè)備可以降低發(fā)送消息的占空比，并且具有能源效率高和可伸縮性的優(yōu)點。此外，該組中的其他設(shè)備仍能保證被快速發(fā)現(xiàn)。
　　這個方案的設(shè)計中有3個主要問題。首先，分散的設(shè)備如何能夠組成一個按序發(fā)送信標(biāo)的群組？其次，設(shè)備是移動的，如何在移動的環(huán)境中維持這個群組？第三，形成一個群組會引進(jìn)額外的能耗，這是否會使弊大于利？
　　對于第一個問題，該方案被分為兩個部分：加入操作和群組操作。加入操作規(guī)定設(shè)備如何選擇群組以及如何被群組接受。群組操作可以調(diào)節(jié)成員列表，比如新成員設(shè)備的添加或從列表中刪除一個成員。如圖2所示，為了實現(xiàn)這兩個操作，引入了3個窗：加入窗、聯(lián)系窗和更新窗。加入窗可以發(fā)現(xiàn)其他設(shè)備，聯(lián)系窗可以進(jìn)行3次握手，更新窗可以通知其他設(shè)備已更新的成員列表。
　　

　　對于第二個問題，該方案引入了增強技術(shù)。在移動環(huán)境中，成員設(shè)備可能頻繁地移動出群組通信范圍。因此，群組可能經(jīng)常重組，這會導(dǎo)致程序崩潰，而且這也不符合能源效率和可擴(kuò)展性的要求。如圖2所示，增強技術(shù)就是假設(shè)A沒有收到B的ACK消息（B的更新窗發(fā)送），A將另外發(fā)送一個信標(biāo)給C，從而降低群組斷鏈重組的頻率。
　　對于第三個問題，該方案只需要設(shè)備保持低占空比，而且隨著群組成員數(shù)量的不斷增加，占空比將不斷降低。
　　3.3藍(lán)牙與WiFi搜索的融合
　　WiFi和藍(lán)牙技術(shù)在節(jié)點搜索中各有優(yōu)缺點。WiFi覆蓋范圍大但能耗也大，而藍(lán)牙能耗雖小但覆蓋范圍也小。為了節(jié)省能量，而又不減小設(shè)備的搜索范圍，可以采用CQuest搜索方案［9］。
　　移動節(jié)點會形成臨時集群，如圖3(a)所示，每個集群成員可以通過WiFi搜索到距離較遠(yuǎn)的另一個集群的所有成員。因此，如圖3(b)所示，CQuest方案是讓每個集群成員采用功耗更低的藍(lán)牙搜索，而只保留其中一個成員的WiFi搜索。
　　

　　CQuest由三個部分組成。
　?。?）每個集群只有選定的設(shè)備需要使用WiFi和藍(lán)牙掃描，其他設(shè)備只使用藍(lán)牙掃描。這個WiFi設(shè)備選擇的基本思路是：每個集群設(shè)備檢查是否有其他成員會在下一輪進(jìn)行WiFi掃描，如果有，該節(jié)點下一輪就不進(jìn)行WiFi掃描，否則，該節(jié)點下一輪開始掃描。這顯然會產(chǎn)生競爭，CQuest提供了詳細(xì)的解決方案，這里不再闡述。
　?。?）關(guān)于每一輪掃描時間的確定，對于有架構(gòu)輔助的同步網(wǎng)絡(luò)，該方案可以使用有固定周期的信標(biāo)，一輪時間就可以定義為固定數(shù)目的周期。對于異步網(wǎng)絡(luò)，可以使用現(xiàn)有的異步鄰居發(fā)現(xiàn)協(xié)議。
　?。?）維持CQuest集群。每個集群成員都有一份集群成員名單列表，所以只要保持它們的列表同步。一旦有節(jié)點加入集群，其他成員的列表都會被更新。CQuest使用兩個閾值來確定是否有成員離開集群。
4開放性研究問題
　　在D2D節(jié)點發(fā)現(xiàn)的過程中，依舊存在著一些研究問題。
　　4.1網(wǎng)絡(luò)輔助和定位
　　利用定位技術(shù)和網(wǎng)絡(luò)云的輔助，可以有效提高節(jié)點搜索效率，例如網(wǎng)絡(luò)服務(wù)器可根據(jù)節(jié)點所在位置分析出周圍是否存在可搜索節(jié)點，若沒有，則關(guān)閉節(jié)點搜索開關(guān)，從而提高搜索效率 ［1011］。
　　4.2節(jié)點搜索與服務(wù)發(fā)現(xiàn)的結(jié)合
　　D2D節(jié)點搜索的目的是為了發(fā)現(xiàn)并傳輸服務(wù)，傳統(tǒng)的服務(wù)發(fā)現(xiàn)方法是搜索到節(jié)點后必須建立連接才可以獲知服務(wù)基本信息。例如，WiFi聯(lián)盟提出了WiFi Direct技術(shù)，該技術(shù)在節(jié)點搜索的信號中添加了服務(wù)信息，實現(xiàn)了節(jié)點搜索與服務(wù)發(fā)現(xiàn)的結(jié)合，使節(jié)點不需要建立連接就可獲得服務(wù)基本信息［12］。
5結(jié)論
　　D2D節(jié)點發(fā)現(xiàn)是D2D通信的重要部分，雖然目前提出了不少解決方案，但是性能上還有很大的提高空間。本文闡述了D2D節(jié)點搜索中的主要問題，針對這些問題總　　結(jié)了一些有代表性的解決方案，最后，列舉了一些熱門的開放性問題。
　　參考文獻(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.
　?。?］ 陳良銀, 顏秉姝, 張靖宇, 等. 移動低占空比傳感網(wǎng)鄰居發(fā)現(xiàn)算法［J］. 軟件學(xué)報, 2014, 25(6): 13521368.
　?。?］ 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.
　　［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.
　?。?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,