鄰近信息約束下的隨機異構(gòu)無線傳感器網(wǎng)絡(luò)節(jié)點調(diào)度算法

秦寧寧; 金磊; 許健; 徐帆; 楊樂

doi:10.11999/JEIT190094

鄰近信息約束下的隨機異構(gòu)無線傳感器網(wǎng)絡(luò)節(jié)點調(diào)度算法

doi: 10.11999/JEIT190094

秦寧寧^1, ,,
金磊¹,
許健¹,
徐帆²,
楊樂³

1.
江南大學(xué)輕工過程先進控制教育部重點實驗室 ??無錫 ??214122
2.
南京航空航天大學(xué)雷達成像與微波光子教育部重點實驗室南京 210016
3.
坎特伯雷大學(xué)電氣與計算機工程系克賴斯特徹奇新西蘭 8011

基金項目: 國家自然科學(xué)基金(61702228)，江蘇省自然科學(xué)基金(BK20170198)，雷達成像與微波光子教育部重點實驗室開放基金(NJ20170001-7)，江蘇省博士后科研資助計劃(1601012A)，江蘇省“六大人才高峰”計劃(DZXX-026)，中央高?；究蒲袠I(yè)務(wù)費專項資金(JUSRP1805XNC)

詳細信息

作者簡介:
秦寧寧：女，1980年生，副教授，碩士生導(dǎo)師，研究方向為無線傳感器網(wǎng)絡(luò)及應(yīng)用

金磊：男，1993年生，碩士生，研究方向為無線傳感器網(wǎng)絡(luò)覆蓋

許?。耗?，1992年生，碩士生，研究方向為無線傳感器網(wǎng)絡(luò)覆蓋

徐帆：男，1988年生，講師，碩士生導(dǎo)師，研究方向為信號處理與應(yīng)用

楊樂：男，1979年生，副教授，碩士生導(dǎo)師，研究方向為無線信號統(tǒng)計與應(yīng)用

通訊作者:
秦寧寧　ningning801108@163.com

中圖分類號: TN929.5
計量
- 文章訪問數(shù): 3000
- HTML全文瀏覽量: 949
- PDF下載量: 69
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2019-02-17
- 修回日期: 2019-06-09
- 網(wǎng)絡(luò)出版日期: 2019-06-14
- 刊出日期: 2019-10-01

Neighbor Information Constrained Node Scheduling in Stochastic Heterogeneous Wireless Sensor Networks

Ningning QIN^{1
, ,},
Lei JIN¹,
Jian XU¹,
Fan XU²,
Le YANG³

1.
Key Laboratory of Advanced Process Control for Light Industry of Ministry of Education, Jiangnan University, Wuxi 214122, China
2.
Key Laboratory of Radar Imaging and Microwave Photonics, Ministry of Education, Nanjing University of Aeronautics and Astronautics, Nanjing 210016, China
3.
Department of Electrical and Computer Engineering, University of Canterbury, Christchurch 8011, New Zealand

Funds: The National Natural Science Foundation of China (61702228), The Natural Science Foundation of Jiangsu Province (BK20170198), The Open Fund of Key Laboratory of Radar Imaging and Microwave Photonics of Ministry of Education (NJ20170001-7), Jiangsu Province Planned Projects for Postdoctoral Research Funds (1601012A), The Eleventh Batch High-level Talents Project of “Six Talent Peaks” in Jiangsu Province(DZXX-026), Fundamental Research Funds for the Central Universities (JUSRP1805XNC)

摘要

摘要: 針對高密度部署的隨機異構(gòu)傳感器網(wǎng)絡(luò)內(nèi)部存在的覆蓋冗余問題，該文提出一種隨機異構(gòu)無線傳感器網(wǎng)絡(luò)的節(jié)點調(diào)度算法(NSSH)。在網(wǎng)絡(luò)原型拓撲的支撐下構(gòu)建Delaunary三角剖分，規(guī)劃出節(jié)點進行本地化調(diào)度的局部工作子集。通過折中與鄰近節(jié)點的空外接圓半徑，完成對感知半徑的獨立配置；引入幾何線、面概念，利用重疊面積和有效約束圓弧完成對灰、黑色節(jié)點的分類識別，使得節(jié)點僅依賴本地及鄰居信息進行半徑調(diào)整和冗余休眠。仿真結(jié)果表明，NSSH能以低復(fù)雜度的代價，近似追平貪婪算法的去冗余性能，并表現(xiàn)出了對網(wǎng)絡(luò)規(guī)模、異構(gòu)跨度和參數(shù)配置的低敏感性。
- 傳感器網(wǎng)絡(luò) /
- 隨機異構(gòu) /
- 覆蓋 /
- 節(jié)點調(diào)度 /
- 鄰近信息
Abstract: Considering coverage redundancy problem existed in random heterogeneous sensor networks with high density deployment, a Node Scheduling algorithm for Stochastic Heterogeneous wireless sensor networks(NSSH) is proposed. The Delaunary triangulation is constructed based on the network prototype topology to work out a local subset of nodes for localization scheduling. Independent configuration of the perceived radius is achieved by discounting the radius of the circumcircle with the adjacent node. The concept of geometric line and plane is introduced, and the overlapping area and the effective constrained arcs are used to classify and identify the grey and black nodes. So the node only relies on local and neighbor information for radius adjustment and redundant node sleep. The simulation results show that NSSH can approximately match the dropping redundancy of greedy algorithm at the cost of low complexity, and exhibit low sensitivity to network size, heterogeneous span and parameter configuration.
- Sensor network /
- Stochastic heterogeneous /
- Coverage /
- Node scheduling /
- Neighbor information

HTML全文

圖 1 節(jié)點${s_i}$的有效約束圓弧${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}$

下載: 全尺寸圖片幻燈片

圖 2 節(jié)點${s_i}$感知半徑${r_i}$調(diào)整圖

下載: 全尺寸圖片幻燈片

圖 3 節(jié)點感知重疊面積求解

下載: 全尺寸圖片幻燈片

圖 4 黑色節(jié)點的標識與計算

下載: 全尺寸圖片幻燈片

圖 5 不滿足圓心$k$覆蓋的節(jié)點約束圓弧圖

下載: 全尺寸圖片幻燈片

圖 6 目標區(qū)域調(diào)整效果對比

下載: 全尺寸圖片幻燈片

圖 7 覆蓋冗余度隨節(jié)點個數(shù)和半徑比變化情況

下載: 全尺寸圖片幻燈片

圖 8 多級異構(gòu)網(wǎng)絡(luò)中$\Delta F\;$的變化

下載: 全尺寸圖片幻燈片

圖 9 二級異構(gòu)網(wǎng)絡(luò)中$\Delta F\;$的變化

下載: 全尺寸圖片幻燈片

圖 10 同構(gòu)網(wǎng)絡(luò)中$\Delta F\;$的變化

下載: 全尺寸圖片幻燈片

表 1 半徑調(diào)整算法步驟

半徑調(diào)整算法(${T^i},{r_i}$)
(1)　$r_{\rm c}^i = \varnothing $
(2)　for $p = 1:P$
(3)　　　calculate the radius $r_{{\rm{cp}}}^i$ of ${T_p}^i$//計算空外接圓半徑
(4)　　　　$r_{\rm c}^i = r_{\rm c}^i \cup r_{ {\rm{cp} } }^i$
(5)　end for
(6　　　${r_i} = \min ({r_i},\max \left( {r_{\rm c}^i} \right))$//若$\max \left( {r_{\rm c}^i} \right) > {r_i}$，則保留原${r_i}$
(7)　return (${r_i}$)

下載: 導(dǎo)出CSV

表 2 NSSH算法步驟

NSSH (${T^i}$,${r_i}$,${\rm{N}}{{\rm{e}}_i}$,${\theta _{{\rm{th}}}}$,${\left\| {{\rm{arc}}} \right\|_{{\rm{th}}}}$,$k$)
(1)　初始化：${\rm{s}}{{\rm{t}}_i} = 1$, ${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}=\varnothing$
(2)　${r_i}$=半徑調(diào)整算法(${T^i},{r_i}$)
(3)　for $q = 1:Q$
(4)　　${\rm{if}}({\theta _{i,jq}} > {\theta _{{\rm{th}}}})$) //基于定義5和式(1)判定灰色節(jié)點
(5)　　　${\rm{s}}{{\rm{t}}_i} = 0$
(6)　　end if
(7)　　${\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}}={\stackrel \frown {{\rm{ar}}{{\rm{c}}_i}}} \cup {\stackrel \frown {{\rm{ar}}{{\rm{c}}_{i\_jq}}}}$ //計算有效約束圓弧
(8)　end for
(9)　calculate $\left\| {{\rm{ar}}{{\rm{c}}_i}} \right\|$ ${k_i}$ //基于式(2)—式(4)計算有效約束圓弧度數(shù)，統(tǒng)計${s_i}$的覆蓋度${k_i}$
(10)　if ($\left\| {{\rm{ar}}{{\rm{c}}_i}} \right\| \ge {\left\| {{\rm{arc}}} \right\|_{{\rm{th}}}}{\rm{\& \& }}{k_i} \ge k$)//基于定義6判定黑色節(jié)點
(11)　　${\rm{s}}{{\rm{t}}_i} = 0$
(12)　end if
(13)　return (${\rm{s}}{{\rm{t}}_i}$)

下載: 導(dǎo)出CSV

表 3 5種算法參數(shù)

算法	節(jié)點數(shù)目
算法	$N = {\rm{100}}$, $N = {\rm{150}}$	$N = {\rm{200}}$, $N = {\rm{250}}$	$N = {\rm{300}}$, $N = {\rm{350}}$	$N = {\rm{400}}$, $N = {\rm{450}}$	$N = {\rm{500}}$
NSSH	${\theta _{{\rm{th}}}} = 0.82$ ${\left\| {{\rm{arc}}} \right\|_{{\rm{th}}}} = 1.96{\text{π}} $ $k{\rm{ = 2}}$
GGA	$\mu {\rm{ = 0}}{\rm{.9}}$
MCLC	$\Delta c < 0.05$
COAN	${r_{{\rm{thr}}}} = 4.4$ ${\eta _{{\rm{thr}}}} = 1.87{\text{π}} $ ${m_{{\rm{thr}}}} = 11$ $k = 1$	${r_{{\rm{thr}}}} = 4.6$ ${\eta _{{\rm{thr}}}} = 1.9{\text{π}} $ ${m_{{\rm{thr}}}} = 12$ $k = 1$	${r_{{\rm{thr}}}} = 4.8$ ${\eta _{{\rm{thr}}}} = 1.93{\text{π}}$ ${m_{t{\rm{hr}}}} = 13$ $k = 1$	${r_{{\rm{thr}}}} = 5.2$ ${\eta _{{\rm{thr}}}} = 1.96{\text{π}} $ ${m_{{\rm{thr}}}} = 13$ $k = 1$	${r_{{\rm{thr}}}} = 5.4$ ${\eta _{{\rm{thr}}}} = 1.98{\text{π}} $ ${m_{{\rm{thr}}}} = 15$ $k = 1$
NDBS	${k_2}({r_1}/{r_2}) = 4$ ${k_2}({r_2}/{r_1}) = 7$ ${k_3}({r_1}/{r_2}) = 7$ ${k_3}({r_2}/{r_1}) = 16$	${k_2}({r_1}/{r_2}) = 4$ ${k_2}({r_2}/{r_1}) = 8$ ${k_3}({r_1}/{r_2}) = 8$ ${k_3}({r_2}/{r_1}) = 16$	${k_2}({r_1}/{r_2}) = 4$ ${k_2}({r_2}/{r_1}) = 7$ ${k_3}({r_1}/{r_2}) = 8$ ${k_3}({r_2}/{r_1}){\rm{ = 15}}$	${k_2}({r_1}/{r_2}) = 3$ ${k_2}({r_2}/{r_1}) = 6$ ${k_3}({r_1}/{r_2}) = 7$ ${k_3}({r_2}/{r_1}) = 14$	${k_2}({r_1}/{r_2}) = 3$ ${k_2}({r_2}/{r_1}) = 6$ ${k_3}({r_1}/{r_2}) = 6$ ${k_3}({r_2}/{r_1}) = 13$
注：表中參數(shù)$\Delta c$代表MCLC算法覆蓋子集的約束條件，${r_{{\rm{thr}}}}$, ${\eta _{{\rm{thr}}}}$, ${m_{{\rm{thr}}}}$僅針對COAN算法，${k_2}({r_1}/{r_2})$, ${k_2}({r_2}/{r_1})$, ${k_3}({r_1}/{r_2})$, ${k_3}({r_2}/{r_1})$僅針對NDBS算法，具體參數(shù)解釋可查閱文獻[8,9]。

下載: 導(dǎo)出CSV

參考文獻(15)

SLIJEPCEVIC S and POTKONJAK M. Power efficient organization of wireless sensor networks[C]. Conference Record IEEE International Conference on Communications, Helsinki, Finland, 2001: 472–476.

付寅飛, 熊慶旭. 綜合路由的無線傳感器網(wǎng)絡(luò)覆蓋調(diào)度[J]. 北京航空航天大學(xué)學(xué)報, 2011, 37(7): 801–804, 838. doi: 10.13700/j.bh.1001-5965.2011.07.004

FU Yinfei and XIONG Qingxu. Coverage-scheduling integrated routing in wireless sensor networks[J]. Journal of Beijing University of Aeronautics and Astronautics, 2011, 37(7): 801–804, 838. doi: 10.13700/j.bh.1001-5965.2011.07.004

韓志杰, 吳志斌, 王汝傳, 等. 新的無線傳感器網(wǎng)絡(luò)覆蓋控制算法[J]. 通信學(xué)報, 2011, 32(10): 174–184. doi: 10.3969/j.issn.1000-436X.2011.10.022

HAN Zhijie, WU Zhibin, WANG Ruchuan, et al. Novel coverage control algorithm for wireless sensor network[J]. Journal on Communications, 2011, 32(10): 174–184. doi: 10.3969/j.issn.1000-436X.2011.10.022

黨小超, 邵晨光, 郝占軍. 半徑可調(diào)的無線傳感器網(wǎng)絡(luò)三維覆蓋算法[J]. 計算機應(yīng)用, 2018, 38(9): 2581–2586, 2615. doi: 10.11772/j.issn.1001-9081.2018020357

DANG Xiaochao, SHAO Chenguang, and HAO Zhanjun. 3D-coverage algorithm based on adjustable radius in wireless sensor network[J]. Journal of Computer Applications, 2018, 38(9): 2581–2586, 2615. doi: 10.11772/j.issn.1001-9081.2018020357

BHATTACHARJEE M and GUPTA S. Determining redundant nodes in a location unaware wireless sensor network[C]. IEEE International Conference on Advanced Communications, Control and Computing Technologies, Ramanathapuram, India, 2014: 858–862.

CHENAIT M, ZEBBANE B, FILALI S, et al. A low-complex coverage eligibility algorithm for wireless sensor networks[C]. International Conference on Intelligent Information Processing, Security and Advanced Communication, Batna, Algeria, 2015: Article No.85. doi: 10.1145/2816839.2816854.

CHENAIT M, ZEBBANE B, and BADACHE N. A new k-coverage model to determine redundant sensors in wireless sensor networks[C]. 2018 International Conference on Smart Communications in Network Technologies (SaCoNeT), El Oued, Algeria, 2018: 149–154.

劉浩然, 趙赫瑤, 鄧玉靜, 等. 基于非合作博弈的無線傳感器網(wǎng)絡(luò)覆蓋控制算法[J]. 通信學(xué)報, 2019, 40(1): 71–78. doi: 10.11959/j.issn.1000-436x.2019006

LIU Haoran, ZHAO Heyao, DENG Yujing, et al. Coverage control algorithm for wireless sensor networks based on non-cooperative game[J]. Journal on Communications, 2019, 40(1): 71–78. doi: 10.11959/j.issn.1000-436x.2019006

賈明偉, 吳敏, 沙超, 等. 節(jié)點相鄰關(guān)系的傳感網(wǎng)覆蓋優(yōu)化方法[J]. 電子測量與儀器學(xué)報, 2015, 29(11): 1574–1583. doi: 10.13382/j.jemi.2015.11.002

JIA Mingwei, WU Min, SHA Chao, et al. Coverage optimization algorithm based on adjacent neighbors for sensor networks[J]. Journal of Electronic Measurement and Instrumentation, 2015, 29(11): 1574–1583. doi: 10.13382/j.jemi.2015.11.002

孫力娟, 魏靜, 郭劍, 等. 面向異構(gòu)無線傳感器網(wǎng)絡(luò)的節(jié)點調(diào)度算法[J]. 電子學(xué)報, 2014, 42(10): 1907–1912. doi: 10.3969/j.issn.0372-2112.2014.10.006

SUN Lijuan, WEI Jing, GUO Jian, et al. Node scheduling algorithm for heterogeneous wireless sensor networks[J]. Acta Electronica Sinica, 2014, 42(10): 1907–1912. doi: 10.3969/j.issn.0372-2112.2014.10.006

高潔, 吳延紅, 白建俠, 等. 無線傳感器網(wǎng)絡(luò)最小覆蓋能量優(yōu)化算法[J]. 傳感技術(shù)學(xué)報, 2016, 29(9): 1435–1440. doi: 10.3969/j.issn.1004-1699.2016.09.024

GAO Jie, WU Yanhong, BAI Jianxia, et al. The minimum coverage energy optimization algorithms in wireless sensor network[J]. Chinese Journal of Sensors and Actuators, 2016, 29(9): 1435–1440. doi: 10.3969/j.issn.1004-1699.2016.09.024

權(quán)恩猛, 吳斌. 基于Delaunay三角剖分的有向傳感器網(wǎng)絡(luò)覆蓋增強算法[J]. 計算機應(yīng)用研究, 2018, 35(8): 2447–2449. doi: 10.3969/j.issn.1001-3695.2018.08.052

QUAN Enmeng and WU Bin. Coverage enhancement algorithm based on delaunay triangulation for directional sensor networks[J]. Application Research of Computers, 2018, 35(8): 2447–2449. doi: 10.3969/j.issn.1001-3695.2018.08.052

杜曉玉, 孫力娟, 郭劍, 等. 異構(gòu)無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法[J]. 電子與信息學(xué)報, 2014, 36(3): 696–702. doi: 10.3724/SP.J.1146.2013.00730

DU Xiaoyu, SUN Lijuan, GUO Jian, et al. Coverage optimization algorithm for heterogeneous WSNs[J]. Journal of Electronics &Information Technology, 2014, 36(3): 696–702. doi: 10.3724/SP.J.1146.2013.00730

刁鵬飛, 王艷嬌. 基于節(jié)點休眠的水下無線傳感器網(wǎng)絡(luò)覆蓋保持分簇算法[J]. 電子與信息學(xué)報, 2018, 40(5): 1101–1107. doi: 10.11999/JEIT170787

DIAO Pengfei and WANG Yanjiao. Coverage-preserving clustering algorithm for underwater sensor networks based on the sleeping mechanism[J]. Journal of Electronics &Information Technology, 2018, 40(5): 1101–1107. doi: 10.11999/JEIT170787

LI Wei and ZHANG Wei. Coverage hole and boundary nodes detection in wireless sensor networks[J]. Journal of Network and Computer Applications, 2015, 48: 35–48. doi: 10.1016/j.jnca.2014.10.011.

相關(guān)文章

施引文獻

資源附件(0)

訪問統(tǒng)計