葉恒舟，郝 薇，黃鳳怡

(桂林理工大學廣西嵌入式技術(shù)與智能系統(tǒng)重點實驗室，廣西 桂林 541006)

1 引言

物聯(lián)網(wǎng)中大量傳感器源節(jié)點從周圍環(huán)境中收集狀態(tài)信息，并將數(shù)據(jù)發(fā)送到數(shù)據(jù)處理中心，數(shù)據(jù)處理中心則根據(jù)接收到的數(shù)據(jù)做出控制決策。這種決策的有效性與所依據(jù)的數(shù)據(jù)的新鮮度密切相關，因而在物聯(lián)網(wǎng)中對數(shù)據(jù)收集時延很敏感。AoI作為新興的數(shù)據(jù)新鮮度度量指標，廣泛應用于對時間敏感的網(wǎng)絡場景中，如車輛網(wǎng)絡、無人機(Unman-ned Aerial Vehicle，UAV)輔助的物聯(lián)網(wǎng)、用于廣播信息的無線網(wǎng)絡、無線工業(yè)網(wǎng)絡中的過程監(jiān)控等。

AoI被定義為當前時間與其在源節(jié)點處生成時間的差值，可以用來描述樣本的整個生命周期。在物聯(lián)網(wǎng)信息收集過程中，為保持數(shù)據(jù)新鮮度，需要合理分配上行容量，以合理規(guī)劃源節(jié)點向數(shù)據(jù)收集中心發(fā)送數(shù)據(jù)的順序。很多學者關注了這個問題，但這些研究存在以下一個或兩個不足：①未考慮到源節(jié)點可能發(fā)生的樣本擠壓問題；②考慮的系統(tǒng)模型與現(xiàn)實物聯(lián)網(wǎng)數(shù)據(jù)采集模型存在差距，所得的結(jié)論不能很好地應用于現(xiàn)實場景。如文獻[7]提出了兩種傳感器調(diào)度策略，一種假設系統(tǒng)參數(shù)已知，另一種假設系統(tǒng)參數(shù)未知而需要學習，都以最小化信源的AoI為優(yōu)化目標。文獻[8]通過將調(diào)度問題分解為多個可計算的子問題，分別提出了靜態(tài)和動態(tài)請求模型的請求感知調(diào)度策略。在文獻[9]中，當有新的樣本到達時，選擇丟棄等待在隊列中的舊數(shù)據(jù)包以提高AoI。文獻[10]考慮了存在等候室與不存在等候室兩種服務設施下，以AoI為指標的允許搶占的資源分配方案。以上策略均未考慮樣本擠壓情況，或是簡單丟棄被擠壓的樣本。另一方面，文獻[10]假設所有源節(jié)點的負載相同，文獻[11]假設所有源節(jié)點的權(quán)重相等，文獻[12]假設所有更新大小相同，這些假設都與實際情況存在一些差距。文獻[13]構(gòu)造了更加貼近現(xiàn)實的系統(tǒng)模型，允許源節(jié)點的權(quán)重、采樣大小以及采樣周期不同，并提出了JUVENTAS算法，將源節(jié)點信息進行調(diào)度傳輸，接近最優(yōu)解，但是該算法也忽視了樣本信息擠壓的情況。

本文考慮文獻[13]中提出的周期性采樣系統(tǒng)模型，在最小化AoI的同時，盡量避免樣本擠壓，設計了一種基于貪心策略的調(diào)度算法，該算法能夠合理規(guī)劃物聯(lián)網(wǎng)中的源節(jié)點與基站之間的上行通信調(diào)度。

2 研究動機

2.1 系統(tǒng)模型

本文考慮一個包含

N

個物聯(lián)網(wǎng)源節(jié)點和一個基站的單跳無線網(wǎng)絡，如圖1所示。每個源節(jié)點周期性地采集數(shù)據(jù)，并在擁有上行帶寬時，向基站傳輸采集到的數(shù)據(jù)。設

S

表示第

i

個源節(jié)點，

S

的采樣周期為

T

，每次采樣的數(shù)據(jù)單元個數(shù)為

L

。基站的上行鏈路采用時分復用技術(shù)，在每個時隙內(nèi)，擁有可以傳輸

M

個PDU(協(xié)議數(shù)據(jù)單元， Protocol Data Unit)的容量。通信調(diào)度的目標是在每個時隙，將上行容量合理分配給各個源節(jié)點。若

x

(

t

)表示

t

時隙時為

S

分配的上行容量，則

x

(

t

)={<1，

x

(

t

)>，<2，

x

(

t

)>，…，<

N

，

x

(

t

)>}可表示

t

時隙時的一種調(diào)度方案。

圖1 系統(tǒng)模型

2.2 樣本擠壓

在上述系統(tǒng)模型中，由于基站的上行容量有限，可能出現(xiàn)如下情況：一個源節(jié)點在開始采集新的樣本時，之前已經(jīng)采集的樣本還沒有完全傳輸?shù)交?。把這種現(xiàn)象稱為樣本擠壓。

設

N

=2，

M

=10，

T

=2，

T

=6，

L

=2，

L

=50，

S

與

S

的權(quán)重分別為4與5，首次采樣時刻都為0，忽略采樣所需要的時間。若采用

JUVENTAS

算法，可以得到如下的調(diào)度方案：

x

(0)={<1， 2>，<2， 8>}，

x

(1)={<1， 0>，<2， 10>}，

x

(2)={<1， 0>，<2， 10>}，

x

(3)={<1， 0>，<2， 10>}，

x

(4)={<1， 0>，<2， 10>}，

x

(5)={<1， 4>，<2， 2>}?？梢园l(fā)現(xiàn)

S

在

t

=2、

t

=4時發(fā)生了樣本擠壓現(xiàn)象。在發(fā)生了樣本擠壓后，若不覆蓋被擠壓的樣本，則需要額外的存儲空間，且會增加

AoI

；若丟失擠壓樣本，意味著增大了源節(jié)點的采樣周期，會對后續(xù)決策產(chǎn)生影響。因此，在設計物聯(lián)網(wǎng)的調(diào)度方案時，不僅要最小化

AoI

，還應盡量避免樣本擠壓。事實上，若采用如下調(diào)度序列，可以避免發(fā)生擠壓現(xiàn)象：

x

(0)={<1， 2>，<2， 8>}，

x

(1)={<1， 0>，<2， 10>}，

x

(2)={<1， 2>，<2， 8>}，

x

(3)={<1， 0>，<2， 10>}，

x

(4)={<1， 2>，<2， 8>}，

x

(5)={<1， 0>，<2， 6>}。

3 AoI模型

AoI

用于度量信息的新鮮程度。記

A

(

t

，

k

)為信息

I

(

k

)在

t

時刻的

AoI

，可由式(1)確定

A

(

t

，

k

)

(1)

其中，

ET

(

k

)表示

I

(

k

)完全被傳輸?shù)交镜臅r刻，

ST

(

k

)表示信息開始采集的時刻。若

I

(

k

)已經(jīng)全部傳輸?shù)交?，取值?p>ET

(

k

)-

ST

(

k

)；若

I

(

k

)尚未采集，取值為0；若

I

(

k

)尚未全部傳輸?shù)交荆≈禐?p>t

-

ST

(

k

)?？梢?，要最小化

A

(

t

，

k

)，關鍵是要盡快將

I

(

k

)完全傳輸?shù)交尽ＴO在

T

個時間段內(nèi)，源節(jié)點

i

共采集了

K

個信息，

A

(

T

)表示在

T

個時間段內(nèi)，源節(jié)點

i

采集的所有信息的

AoI

之和。則

A

(

T

)可由式(2)計算

(2)

若這

K

個信息中，前

j

個已經(jīng)全部傳輸?shù)搅嘶荆Ｓ嗟纳形慈總鬏數(shù)交?，則

A

(

T

)可由式(3)度量

(3)

考慮到源節(jié)點所傳輸?shù)男畔⒌闹匾潭瓤赡艽嬖诓町?，設源節(jié)點

i

的權(quán)重為

W

。

w

為

W

歸一化的結(jié)果，可由式(4)獲得

(4)

(5)

4 樣本擠壓模型

(6)

對于Juventas算法，下面的定理1表明：當同時存在采樣周期比較短的源節(jié)點，以及采樣數(shù)據(jù)比較多的源節(jié)點時，比較容易發(fā)生擠壓現(xiàn)象。

定理1：設

N

≥ 2，若存在

i

，

j

，滿足

L

> 2 *

T

*

M

，則對于Juventas算法，必定會產(chǎn)生擠壓現(xiàn)象。證明：因為各源節(jié)點周期性采樣，必定存在某個時刻

t

，源

i

與

j

同時采樣，即在時刻

t

，

WT

≥ 1且

WT

≥ 1。分別考慮如下兩種情況中：

綜上所述，對于Juventas算法，在足夠長的時間范圍內(nèi)，源

i

必定會發(fā)生擠壓現(xiàn)象。事實上，對于源節(jié)點

i

，若

L

較大時，

T

也較大，可以設計調(diào)度算法有效避免或減緩擠壓現(xiàn)象的發(fā)生。這可由下面的定理2證實。

5 調(diào)度算法設計

5.1 △Ai(t，k)度量

設

t

時隙之前，源節(jié)點

i

上前

k

-1個采集樣本已經(jīng)全部傳輸?shù)搅嘶?，而剩余的尚未傳輸或尚未全部傳輸?shù)交?。根?jù)式(3)，在

t

時隙時，是否允許源節(jié)點

i

傳輸數(shù)據(jù)，只會對第

k

個樣本產(chǎn)生影響。

(7)

(8)

由于只有當樣本

k

全部傳輸至基站，其

AoI

才會不再增加，因此，為降低

AoI

，應優(yōu)先調(diào)度可以全部傳輸?shù)交康脑垂?jié)點上的樣本，即滿足

RL

<

M

的源節(jié)點。其中，

RL

表示源節(jié)點

i

傳輸完當前等待傳輸?shù)臉颖舅枰膸捹Y源。另一方面，只有當源站存在等待傳輸?shù)臉颖緯r，允許其傳輸樣本才有價值，因此，應優(yōu)先調(diào)度

T

最小的源節(jié)點。綜合來看，可以考慮優(yōu)先調(diào)度能夠使

T

-

RL

/M

最小的源節(jié)點樣本。

5.2 △OTi(t，k)度量

對于一個已經(jīng)被采集等待傳輸?shù)臉颖荆斊渌谠垂?jié)點處存在擠壓現(xiàn)象且當前時隙可以將此樣本傳輸完畢時，若允許傳輸，樣本擠壓數(shù)目會減少一個，相較不傳輸而言，樣本擠壓增益為1；當其源節(jié)點不存在擠壓現(xiàn)象或當前時隙不可以將此樣本傳輸完畢時，傳輸與否樣本擠壓數(shù)目都不會發(fā)生改變，樣本擠壓增益為0。因此，樣本擠壓增益Δ

OT

(

t

，

k

)可由式(9)描述

(9)

其中，

RM

(

t

)表示

t

時隙上行鏈路的剩余帶寬容量，

RL

(

k

)表示源節(jié)點

i

處

t

時刻等待傳輸?shù)臉颖?p>I

(

k

)剩余未傳輸?shù)腜DU數(shù)量?？梢钥闯?，若所傳輸樣本的源節(jié)點處不存在擠壓現(xiàn)象，樣本擠壓增益為0，只有調(diào)度存在擠壓的源節(jié)點樣本才會產(chǎn)生相應的增益，應盡力去傳輸最有可能導致發(fā)生擠壓或擠壓最為嚴重的源節(jié)點樣本。源節(jié)點采樣周期較傳輸此源節(jié)點上所有剩余等待傳輸?shù)腜DU所用時間越小，意味著一個周期內(nèi)將剩余PDU傳輸完畢越困難，此源節(jié)點發(fā)生擠壓可能性越大。因而，優(yōu)先調(diào)度能夠使

T

-

RL

/M

最小的源節(jié)點樣本，可有效避免或減緩擠壓現(xiàn)象的發(fā)生。

5.3 調(diào)度算法

算法1

AEA

輸入：

W

、

L

、

T

、

t

、

N

、

M

輸出：

x

(

t

)1)

RM

=

M

；2)

while

(

RM

> 0)

4) 若

i

不存在，退出

while

循環(huán)；5)

if

(

RL

<=

RM

)6) 添加<

i

，

RL

>至

x

(

t

)；7)

WT

(

t

)--；8)

RM

=

RM

-

RL

；9)

else

10) 添加<

i

，

RM

>至

x

(

t

)；11)

RM

=0；12)

RL

=

RL

-

RM

；13)

end

if

14)

end

while

15) 若源節(jié)點

j

未被調(diào)度，添加<

j

， 0>至

x

(

t

)；16) 輸出

x

(

t

)；

6 實驗分析

實驗運行環(huán)境為Interl (R) Core (TM) i7-4720HQ、2.60GHz CPU、8GB內(nèi)存、64位Windows10操作系統(tǒng)的PC機，編程語言為Java1.7。

考慮兩種場景：一種是與文獻[13]相同(記為G1，如表1所示)，另一種包含大樣本的源節(jié)點(記為G2，如表2所示)。從AoI之和的加權(quán)平均值以及平均擠壓樣本數(shù)兩個方面對比本文的算法AEA與文獻[13]的算法JUVENTAS。當出現(xiàn)樣本擠壓現(xiàn)象時，采取的是不丟棄任何樣本的策略。算法的持續(xù)時間可保證每個源節(jié)點至少采樣100次。

表1 G1場景

表2 G2場景

6.1 平均擠壓樣本數(shù)對比

圖2對比了兩種算法在

G

1時的樣本擠壓情況。當

M

較大(大于35)時，兩種算法都很少發(fā)生擠壓情況。隨著

M

的減少，算法

JUVENTAS

的擠壓現(xiàn)象越來越嚴重，但對于算法

AEA

，在

M

大于13之前，不會發(fā)生擠壓現(xiàn)象。當

M

更小時，算法

AEA

的擠壓現(xiàn)象也明顯優(yōu)于算法

JUVENTAS

。

圖2 鏈路容量對平均擠壓樣本數(shù)的影響對比(G1)

圖3則對比了

G

2時的情景，呈現(xiàn)出了與圖2類似的情況。只是在

G

2時，當

M

位于[13， 21]之間時，算法

AEA

仍然沒有發(fā)生擠壓現(xiàn)象，但算法

JUVENTAS

的擠壓現(xiàn)象與已經(jīng)很嚴重(當M=14時，平均擠壓樣本數(shù)已經(jīng)達到25)。當M更小時，兩種算法都會出現(xiàn)嚴重的擠壓現(xiàn)象。

綜合分析可得：當M很大時，不論哪種算法，樣本擠壓現(xiàn)象都很少發(fā)生，考慮樣本擠壓的意義不大；當M很小時，兩種算法都不能很好避免樣本擠壓問題，這里的核心問題應該是增加M，或者減少源節(jié)點規(guī)模，即N；而當M不大不小時，算法AEA顯然能夠很好地避免樣本擠壓問題。

圖3 鏈路容量對平均擠壓樣本數(shù)的影響對比(G2)

6.2 平均AoI對比

圖4對比了兩種算法在兩種場景下，平均AoI隨鏈路容量M的變化情況。當M較大時，AoI受M的影響較小，甚至不再隨著M的增大而減小；當M較小時，AoI會隨M的減少而增加，且趨勢越來越明顯。這表明對于一個固定的物聯(lián)網(wǎng)，鏈路容量的合理取值應該位于一個區(qū)間，而正是在這個區(qū)間，算法對樣本擠壓比較敏感。

圖4 鏈路容量對平均AoI的影響(G1與G2)

從圖4可以看出，當M較小時，算法

AEA

可以獲得比算法

JUVENTAS

更好的

AoI

。這是因為

JUVENTAS

直接采用基于式(8)的貪心策略，表面上看單個源節(jié)點可以獲得更好的

AoI

增益，但當擠壓現(xiàn)象比較嚴重時，那些本來可以快速傳輸至基站從而停止增加

AoI

的樣本不得不滯留在源節(jié)點而累積

AoI

。對于

G

1和

G

2，算法

AEA

在

AoI

最小化方面更具優(yōu)勢。圖5描述了當鏈路容量為50，兩種算法的平均

AoI

隨時間變化情況。兩種算法的

AoI

均隨著時間的增加而增加，但算法

AEA

的增速要慢于算法

JUVENTAS

。對比

G

1與

G

2，兩種算法都在

G

1時獲得更低的增速，這表明具有大樣本的場景更容易帶來更大的平均

AoI

。

圖5 持續(xù)時間對平均AoI的影響(G1與G2)

7 結(jié)束語

本文考慮了包含一個基站與多個源節(jié)點的物聯(lián)網(wǎng)系統(tǒng)，每個源節(jié)點周期性地采集樣本，并在合適的時候傳輸至基站。在基站的傳輸帶寬受限時，如何合理地將帶寬分配給各個源節(jié)點，影響系統(tǒng)的長期平均

AoI

，也決定著系統(tǒng)中是否會發(fā)生樣本擠壓或其嚴重程度?；谪澬牟呗裕O計了一種

AoI

及樣本擠壓感知的帶寬分配策略。仿真驗證了算法的有效性。物聯(lián)網(wǎng)節(jié)點往往是能量受限的，而數(shù)據(jù)傳輸基于無線傳輸信道，因而通信調(diào)度策略還需關注節(jié)點的能耗與信道可靠性問題，這是下一步的關注重點。