網(wǎng)內(nèi)聚集(數(shù)據(jù)庫(kù))

時(shí)間：2022-11-28 12:30:02 | 來(lái)源：信息時(shí)代

時(shí)間：2022-11-28 12:30:02 來(lái)源：信息時(shí)代

    網(wǎng)內(nèi)聚集 : 在感知查詢處理過(guò)程中,傳感器節(jié)點(diǎn)對(duì)接收的數(shù)據(jù)進(jìn)行部分聚集處理,例如,MAX、MIN、MEDIAN、AVG、SUM等操作,然后將處理后的結(jié)果進(jìn)一步轉(zhuǎn)發(fā)給其父親節(jié)點(diǎn)。匯聚節(jié)點(diǎn)最終接收到經(jīng)過(guò)各級(jí)傳感器節(jié)點(diǎn)聚集處理過(guò)的數(shù)據(jù)。
無(wú)線傳感器網(wǎng)絡(luò)中主要的聚集處理技術(shù)包括集中式聚集處理技術(shù)和網(wǎng)內(nèi)聚集處理技術(shù)。在集中式聚集處理技術(shù)中,所有的傳感器節(jié)點(diǎn)首先將感知到的數(shù)據(jù)傳送到匯聚節(jié)點(diǎn),然后再由匯聚節(jié)點(diǎn)執(zhí)行全局聚集操作處理。例如,求某個(gè)時(shí)刻網(wǎng)絡(luò)所有節(jié)點(diǎn)感知的最高溫度,其聚集函數(shù)為MAX。集中式聚集處理技術(shù)在匯聚節(jié)點(diǎn)處收集所有傳感器節(jié)點(diǎn)的感知數(shù)據(jù),并進(jìn)行MAX操作獲得聚集結(jié)果。網(wǎng)內(nèi)聚集是減少傳感器網(wǎng)絡(luò)中數(shù)據(jù)通信量的有效方法之一。利用網(wǎng)內(nèi)聚集可以大大減少數(shù)據(jù)的傳輸量,從而節(jié)省了通信能耗,并延長(zhǎng)了網(wǎng)絡(luò)和整個(gè)應(yīng)用系統(tǒng)的壽命。對(duì)于例如MAX、MIN、MEDIAN、AVG、SUM等的聚集操作,可以采用網(wǎng)內(nèi)聚集處理技術(shù)。網(wǎng)內(nèi)聚集技術(shù)又包括:
(1)被動(dòng)式聚集處理技術(shù):在路由樹(shù)上,每個(gè)節(jié)點(diǎn)被動(dòng)地等待到其下游(孩子)節(jié)點(diǎn)傳輸?shù)臄?shù)據(jù),對(duì)自己感知的數(shù)據(jù)和下游節(jié)點(diǎn)的數(shù)據(jù)進(jìn)行聚集處理,并將聚集結(jié)果傳輸給其上游(父親)節(jié)點(diǎn)。例如,當(dāng)聚集函數(shù)為MAX時(shí),分布式聚集處理技術(shù)是讓每個(gè)傳感器節(jié)點(diǎn)完成局部聚集操作,即每個(gè)節(jié)點(diǎn)將該節(jié)點(diǎn)采集的數(shù)據(jù)與其子節(jié)點(diǎn)上傳到本地的數(shù)據(jù)進(jìn)行比較,選取最大值轉(zhuǎn)發(fā)給它的父親節(jié)點(diǎn)。于是,每個(gè)時(shí)刻匯聚節(jié)點(diǎn)得到網(wǎng)絡(luò)感知的最高溫度。
(2)基本主動(dòng)式聚集處理技術(shù):傳感器網(wǎng)絡(luò)設(shè)定固定的時(shí)間段,在每個(gè)指定的時(shí)間段內(nèi),每個(gè)非葉子節(jié)點(diǎn)主動(dòng)地將前一時(shí)間間隔內(nèi)計(jì)算的局部聚集結(jié)果上傳給上游節(jié)點(diǎn)。沒(méi)有接收到聚集請(qǐng)求的節(jié)點(diǎn)監(jiān)聽(tīng)到了其他節(jié)點(diǎn)發(fā)送的部分聚集結(jié)果后,也將向上傳送該節(jié)點(diǎn)的聚集結(jié)果。不同于被動(dòng)式聚集處理技術(shù),非葉子節(jié)點(diǎn)不必在等待其下游節(jié)點(diǎn)響應(yīng)后再進(jìn)行數(shù)據(jù)的上傳。主動(dòng)式聚集處理技術(shù)可以避免因下游節(jié)點(diǎn)失效而造成的計(jì)算不準(zhǔn)確問(wèn)題。
主動(dòng)式集聚處理技術(shù)也被稱(chēng)為流水線聚集處理技術(shù)。這種主動(dòng)式、分時(shí)間段上傳數(shù)據(jù)的方式具有兩個(gè)特性: ①每個(gè)時(shí)間段都會(huì)有新的聚集操作被執(zhí)行: ②當(dāng)時(shí)間段設(shè)置很小時(shí),匯聚節(jié)點(diǎn)可以連續(xù)獲得網(wǎng)絡(luò)產(chǎn)生的新的聚集結(jié)果。采用主動(dòng)式聚集處理技術(shù),用戶可以從整個(gè)網(wǎng)絡(luò)獲得連續(xù)的聚集結(jié)果,這種流式數(shù)據(jù)能實(shí)時(shí)地反映傳感器網(wǎng)絡(luò)的變化情況,通常比單一的聚集結(jié)果更有意義。
基本的主動(dòng)式聚集技術(shù)與被動(dòng)式聚集處理技術(shù)相比,要傳送大量的額外信息。
(3)改進(jìn)的主動(dòng)式聚集處理技術(shù):節(jié)點(diǎn)有選擇地上傳聚集數(shù)據(jù),減少通信量。例如,只有在子樹(shù)的聚集結(jié)果發(fā)生改變時(shí),才進(jìn)行本地聚集操作; 只有接收到的數(shù)據(jù)會(huì)影響本地產(chǎn)生的聚集結(jié)果時(shí)才將聚集結(jié)果上傳; 傳感器節(jié)點(diǎn)可以利用共享無(wú)線通道,監(jiān)聽(tīng)附近節(jié)點(diǎn)的通信情況,一旦發(fā)現(xiàn)其他節(jié)點(diǎn)正在發(fā)送聚集數(shù)據(jù),就主動(dòng)參加聚集處理。在使用改進(jìn)的主動(dòng)式聚集處理技術(shù)時(shí),用戶需要定義可以容忍的聚集值的誤差范圍。如果忽略一個(gè)傳感器的數(shù)據(jù)仍能使聚集結(jié)果保持在誤差范圍內(nèi),則該節(jié)點(diǎn)的數(shù)據(jù)就不需要發(fā)送。但是,并不是所有的聚集操作都可以改進(jìn)的主動(dòng)式聚集處理技術(shù),例如,SUM和COUNT一類(lèi)聚集操作是不能應(yīng)用改進(jìn)的主動(dòng)式聚集處理技術(shù)。其原因在于,對(duì)于這一類(lèi)聚集操作,每個(gè)參與計(jì)算的傳感器節(jié)點(diǎn)數(shù)據(jù)都能夠影響最終聚集結(jié)果。
網(wǎng)內(nèi)聚集算法根據(jù)其聚集策略的不同,可分為四類(lèi):
(1)定向擴(kuò)散式網(wǎng)內(nèi)聚集:基本思想是:采用屬性值對(duì)(attribute value pair,AVP)方式描述傳感器的感知數(shù)據(jù),稱(chēng)之為命名數(shù)據(jù)。所有網(wǎng)絡(luò)通信都基于命名數(shù)據(jù)的擴(kuò)散方式進(jìn)行。匯聚節(jié)點(diǎn)針對(duì)命名數(shù)據(jù)提出查詢請(qǐng)求,并廣播通知給網(wǎng)絡(luò)中的所有節(jié)點(diǎn)。只有符合查詢請(qǐng)求的節(jié)點(diǎn)的感知數(shù)據(jù)才被提取。感知數(shù)據(jù)在節(jié)點(diǎn)本地進(jìn)行聚集,并采用兩種方法減小網(wǎng)絡(luò)內(nèi)數(shù)據(jù)擴(kuò)散時(shí)的能量消耗: ①增加式自適應(yīng)路徑選擇策略:通信之前建立一個(gè)梯度場(chǎng),開(kāi)始通信時(shí)節(jié)點(diǎn)沿多條路徑向匯聚節(jié)點(diǎn)傳輸數(shù)據(jù),然后該節(jié)點(diǎn)從這些路徑中選擇一條最優(yōu)路徑作為最終的通信路徑; ②網(wǎng)內(nèi)數(shù)據(jù)緩存策略: 在興趣查詢傳播過(guò)程中,節(jié)點(diǎn)可以選擇緩存或者傳送數(shù)據(jù),也可以根據(jù)之前緩存的數(shù)據(jù)轉(zhuǎn)發(fā)請(qǐng)求。因此,該聚集方式能夠減少動(dòng)態(tài)傳感器網(wǎng)絡(luò)的能量消耗,同時(shí)提高網(wǎng)絡(luò)內(nèi)各個(gè)節(jié)點(diǎn)的配置效率。
(2)啟發(fā)式網(wǎng)內(nèi)聚集:匯聚節(jié)點(diǎn)在傳感器網(wǎng)絡(luò)中建立和維護(hù)一棵聚集樹(shù)。為減少?gòu)V播消息數(shù)量,關(guān)閉樹(shù)中所有葉子節(jié)點(diǎn)的射頻單元以便延長(zhǎng)傳感器網(wǎng)絡(luò)的生命周期。只有非葉子節(jié)點(diǎn)參與數(shù)據(jù)聚集和消息傳輸。每個(gè)節(jié)點(diǎn)根據(jù)剩余能量確定發(fā)送數(shù)據(jù)之前的等待時(shí)間,剩余能量越高,等待時(shí)間越短,成為非葉子節(jié)點(diǎn)的概率越大。該聚集策略有效地節(jié)省了非葉子節(jié)點(diǎn)的能耗,并提高了數(shù)據(jù)傳輸?shù)男?。另?節(jié)點(diǎn)部署密度越大,網(wǎng)絡(luò)壽命越長(zhǎng),擴(kuò)展性越好。但是,采用該策略時(shí),必須考慮使節(jié)點(diǎn)分布盡量均勻,并確保非葉子節(jié)點(diǎn)處于正常工作狀態(tài)。否則,當(dāng)外部事件發(fā)生時(shí),如果不能及時(shí)喚醒處于休眠狀態(tài)的非葉子節(jié)點(diǎn),則系統(tǒng)的響應(yīng)能力將會(huì)受到嚴(yán)重的影響。
(3)增量式網(wǎng)內(nèi)聚集:在傳感器網(wǎng)絡(luò)中建立一棵貪婪增量樹(shù)(greedy incremental tree,GIT)。該樹(shù)提供第一個(gè)感知節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的一條最短路徑,其他節(jié)點(diǎn)均增量式地連接到增量樹(shù)中最近的節(jié)點(diǎn)上。通過(guò)不斷地調(diào)整聚集節(jié)點(diǎn)的位置來(lái)增加路徑共享的數(shù)量,使得通信量最小。與定向擴(kuò)散式網(wǎng)內(nèi)聚集策略相比較,在傳感器網(wǎng)絡(luò)密度較大時(shí),GIT方法可以節(jié)省更多的能量,并且不會(huì)對(duì)延遲和魯棒性造成過(guò)大影響。
(4)折中式網(wǎng)內(nèi)聚集:針對(duì)數(shù)據(jù)聚集的能耗和結(jié)果準(zhǔn)確性之間的平衡問(wèn)題提出一種樹(shù)結(jié)構(gòu)構(gòu)建策略。通過(guò)感知數(shù)據(jù)的時(shí)空關(guān)聯(lián)性,對(duì)部分聚合函數(shù)進(jìn)行低能耗計(jì)算。該策略通過(guò)能耗和準(zhǔn)確性的折中思想,在較低能耗的同時(shí),保持較高的聚集準(zhǔn)確性。