スライド 1

1
センサーネットワークの効率化を実現する
自律分散型マルチホップ送信手法
上智大学理工学部機械工学科管理工学研究グループ４年
A0571215 河野竜一
2
研究背景：センサーネットワークとは
小型無線装置内蔵
センサー
応用例：
森林内火災検知，作業員安全管理など
課題：
エネルギーが有限(電池で稼働)
効率のよい送信路設計アルゴリズムの構築
情報
利用者
3
研究背景：電力消費モデル
小型無線装置内蔵
距離：d(m)
センサー
送信データ：K(bit)
・送信電力=Eelec×K + E(d) ×K×dn(d)
・受信電力=Eelec×K
・圧縮電力=EAD×K×メッセージ数
4
目的
接続性を損なわないようにした上で，従来手法と比
べてシステムの稼働期間が長いデータ送信路設計
アルゴリズムを提案．
システムの稼働期間
1 最初にセンサーが電池切れをおこすまで
2 全てのセンサーが電池切れをおこすまで
5
目的
接続性を損なわないようにした上で，従来手法と比
べてシステムの稼働期間が長いデータ送信路設計
アルゴリズムを提案．
システムの稼働期間
1 最初にセンサーが電池切れをおこすまで
2 全てのセンサーが電池切れをおこすまで
6
センサーネットワークにおける情報収集
①探索領域内に無線装置内蔵
センサーを散布、または配置．
②ネットワークを形成．
③センサーが周辺の情報(温
度や湿度など)を採取．
④無線装置が採取した情報を
ベースステーションへ送信．
⑤ ②③④を繰り返す．
探索領域
ベースステーション
7
センサーネットワークにおける情報収集
センサー
①探索領域内に無線装置内蔵
センサーを散布、または配置．
②ネットワークを形成．
③センサーが周辺の情報(温
度や湿度など)を採取．
④無線装置が採取した情報を
ベースステーションへ送信．
⑤ ②③④を繰り返す．
探索領域
ベースステーション
8
センサーネットワークにおける情報収集
センサー
①探索領域内に無線装置内蔵
センサーを散布、または配置．
②ネットワークを形成．
③センサーが周辺の情報(温
度や湿度など)を採取．
④無線装置が採取した情報を
ベースステーションへ送信．
⑤ ②③④を繰り返す．
探索領域
ベースステーション
9
センサーネットワークにおける情報収集
センサー
①探索領域内に無線装置内蔵
センサーを散布、または配置．
②ネットワークを形成．
③センサーが周辺の情報(温
度や湿度など)を採取．
④無線装置が採取した情報を
ベースステーションへ送信．
⑤ ②③④を繰り返す．
探索領域
ベースステーション
10
センサーネットワークにおける情報収集
センサー
①探索領域内に無線装置内蔵
センサーを散布、または配置．
②ネットワークを形成．
③センサーが周辺の情報(温
度や湿度など)を採取．
④無線装置が採取した情報を
ベースステーションへ送信．
⑤ ②③④を繰り返す．
探索領域
ベースステーション
11
センサーネットワークにおける情報収集
センサー
①探索領域内に無線装置内蔵
センサーを散布、または配置．
②ネットワークを形成．
③センサーが周辺の情報(温
度や湿度など)を採取．
④無線装置が採取した情報を
ベースステーションへ送信．
⑤ ②③④を繰り返す．
探索領域
ベースステーション
12
本研究の位置づけ
送信手法
Ｈop数
Headの数
電力残量の考
慮
年
[1]LEACH
クラスタリング
2hop
全体の5%
無
2002
[2]HEED
クラスタリング
2hop
制限なし
有
2004
Proposal
マルチホップ
制限なし
基本１つ
有
2008
[1]Heinzelman, Pchandrakasan and Balakrishnan : An applicationspecific protocol architecture for wireless microsensor networks. IEEE
transactions on wireless Communications, (2002)
[2]Younis and Fahmy, : Distributed clustering in ad-hoc sensor
networks: A Hybrid, Energy-efficient Approach. in Proceedings of IEEE
INFOCOM, (2004)
13
クラスタリングとは
センサー
クラスタ
ベースステーション
クラスタヘッド
14
従来のクラスタリング手法の特徴
長所
送信スケジュールの構築が確実で簡単．
短所
クラスタの位置やサイズに偏りが出る．
平均送信距離が長くなる．
ラウンドごとにネットワーク形成のための電力が必要．
15
提案手法の特徴
1.最も電池残量の多いセンサーがBSへ情報送信する．
最も電力消費が激しいのがベースステーション
へのデータ送信のため．
2.データ送信は出来るだけマルチホップで行う．
後述．
3.同じネットワークで数ラウンドデータ送信を繰返す．
ネットワーク形成にかかる電力を抑えるため．
16
データ送信をマルチホップで行う理由
・A,Bの情報をCへ送信する場合を考える．
A
パターン１：1hop
dAC
C
A→C、B→C
dBC
B
消費電力
E1hop  Eelec  K  E(d )  K  d AC
Aの送信電力
n( d )
 Eelec  K  E(d )  K  d BC
Bの送信電力
n( d )
 2  Eelec  K
Cの受信電力
17
データ送信をマルチホップで行う理由
・A,Bの情報をCへ送信する場合を考える．
A
パターン2：2hop
A→B→C
C
dAB
dBC
B
消費電力
E2hop  Eelec  K  E(d )  K  d AB
Aの送信電力
n( d )
 Eelec  K  E(d )  K  d BC
n( d )
Bの送受信電力
 Eelec  K  Eelec  K
Cの受信電力
18
データ送信をマルチホップで行う理由
・A,Bの情報をCへ送信する場合を考える．
パターン１：1hop
パターン２:2hop
dAC
A
A
dBC
C
dAB
B
C
B
E1hop  E2 hop  Eelec  K  E (d )  K  d AC

dBC
n( d )
 Eelec  K  E (d )  K  d AB
 E (d )  K  d AC

n( d )
 d AB
 Eelec  K  E (d )  K  d BC
n( d )
n(d )

n(d )
 Eelec  K  E (d )  K  d BC
 2  Eelec  K
n(d )
 Eelec  K  Eelec  K
dAC>dABならば、全体で見れば2hopで送信した方が
電力消費は抑えられる。

19
提案手法の特徴
1.最も電池残量の多いセンサーがBSへ情報送信する．
2.データ送信は出来るだけマルチホップで行う．
3.同じネットワークで数ラウンドデータ送信を繰返す．
20
提案手法のアルゴリズム
探索領域
ベースステーション
21
提案手法のアルゴリズム
①Head決定
Ti=(1-Ei/Eini)×sensor数+i/sensor数
の時刻にHeadに立候補する．
Head
探索領域
ベースステーション
22
提案手法のアルゴリズム
①Head決定
②ADVメッセージの送信
全センサーにHeadとなったことを知ら
せるADVメッセージを送信する．
探索領域
ベースステーション
23
提案手法のアルゴリズム
①Head決定
② ADVメッセージの送信
③第一世代決定
Headとの距離がRADV以下で距離が近
い順のReMAX個のセンサーはHeadを
送信先に決定する．
RAdv
探索領域
ベースステーション
24
提案手法のアルゴリズム
①Head決定
② ADVメッセージの送信
③第一世代決定
RAdv
④第一世代がADVメッセージ送信
第一世代のセンサーがRADVの範囲に
ADVメッセージを送信する．
探索領域
ベースステーション
25
提案手法のアルゴリズム
①Head決定
② ADVメッセージの送信
③第一世代決定
④第一世代がADVメッセージ送信
⑤第二世代決定
メッセージを受け取った距離が近い
ReMAX個までのセンサーは送信先を
決定する．
探索領域
ベースステーション
26
提案手法のアルゴリズム
①Head決定
② ADVメッセージの送信
③第一世代決定
④第一世代がADVメッセージ送信
⑤第二世代決定
⑥繰り返し
最大世代数GMAXに到達するまでメッ
セージ送信→送信先決定を繰り返す．
外れセンサー
探索領域
ベースステーション
27
提案手法のアルゴリズム
①Head決定
② ADVメッセージの送信
③第一世代決定
④第一世代がAdv-Message送信
⑤第二世代決定
⑥繰り返し
⑦情報収集
同ネットワークで数回情報収集を繰り
返す．
外れセンサー
探索領域
ベースステーション
28
提案手法のフローチャート
Ti  1  Ei Einitial  sensor数  i sensor数
Tiまで待機
T<TiでAdv-Message
(HeadID)を受信
No
Head立候補フェーズ
T=Ti:HeadID=i、BSを送信先に決定
Adv-Message(HeadID)を送信
Request-Messageを受信
Yes
d(i,Head)<Adv-Range
No
Yes
送信先=HeadIDに決定
Request-Messageを送信
Permit-Message(世代,TDMA)を受信
世代<世代max
No
Yes
Adv-Message(ID,世代)を送信
Request-Messageを受信
Adv-Messageを受信するまで待機
Permit-Message
(世代、TDMA)を送信
No
Adv-Message(ID,世代)
を受信
Yes
d(i,ID)が最小のIDを送信先に決定
世代=世代
Request-Messageを送信
送信先=BSに決定
ネットワーク形成フェーズ
No
Yes
Permit-Message(世代,TDMA)を送信
TDMAスケジュールに
従って情報送信
情報収集フェーズ
29
ネットワークの例
・最大送信距離RADV=20
・最大受信数ReMAX=4
・最大世代数GMAX=20
の場合
30
問題設定
・センサー数N=100
・BSの座標=(50,175)
・Data量K(bit)=2000
・探索領域の広さW(m)=100×100
・初期電力Eini(J)=0.5
・制御信号量C(bit)=300
・Eelec(nJ/bit)=50
・EAD(nJ/bit/message)=5
・E(d)(pJ/bit/dn(d))=10(d≦87),0.0013(d＞87)
・n(d)=2(d≦87),4(d＞87)
・最大送信距離RADV(m)=30 ・最大受信数ReMAX=2
・最大世代数GMAX=20
・繰り返し数Niter=40
31
従来手法との比較
最初にセンサーが電池切れを起こすラウンド
LEACH
574
HEED
604
proposal
1526
全てのセンサーが電池切れを起こすラウンド
LEACH
2033
HEED
2110
proposal
2779
外れセンサーの数が多
くなるため，センサーの
減少量は従来手法と変
わらない．
32
従来手法との比較(センサー生存数)
proposal
LEACH
HEED
センサー生存数
100
80
60
40
20
0
0
500 1000 1500 2000 2500 3000
ラウンド
33
従来手法との比較(総送信情報量)
2.5E+05
proposal
LEACH
HEED
総送信情報数
2.0E+05
1.5E+05
1.0E+05
5.0E+04
0.0E+00
0
500 1000 1500 2000 2500 3000
ラウンド
34
まとめ
・クラスタリングを用いないマルチホップ送信手法を
提案し，従来手法と比べて長い期間センサーネット
ワークシステムを稼働できることをシミュレーション
によって実証した．
今後の課題
外れセンサーの数を小さくするか，外れセンサーも
他のセンサーを経由できるアルゴリズムの考案．
繰返しデータ送信をしている最中に中継センサーが
電池切れした場合にネットワークを再形成できるア
ルゴリズムの考案．

Download Report