論文

受信端末始動通信による非同期型フラッディングプロトコルの提案とシミュレーション評価中川正基† a)

慶田朗†

田中久陽† b)

Design and Simulation Analysis of an Asynchronous Flooding Protocol
Based on Receiver-Initiated Media Access Control
Masaki NAKAGAWA†a) , Akira KEIDA† , and Hisa-Aki TANAKA†b)

あらまし ユビキタスセンサネットワークや Internet of Things（IoT）などの自律分散ネットワークにおいて，データパケットを全ての端末（ノード）に伝達させる全ノード（マルチホップ）ブロードキャストは一つの重要な基本要素である．全ノードブロードキャストにおいて，CSMA/CA などの送信端末始動通信は，隠れ端末問題を生じることが知られている．そのため，全ノードブロードキャストに受信端末始動通信を用いて隠れ端末問題を回避する研究が行われてきている．しかしながら，これらの研究においては，ネットワークが定常的であり，(1) 各端末がローカルなネットワーク情報を保持する，あるいは (2) 全端末があらかじめ間欠通信タイミ
ングのゆるい同期を行う，などの強い前提がおかれていた．これに対し，本研究は以上の (1)，(2) のいずれの前提も必要としない全ノードブロードキャストのアルゴリズムを提案し，その性能評価を与える．すなわち，系統的なシミュレーションにより本手法の長所，限界，欠点を明らかにし，更に従来の代表的な送信端末始動通信の例（B-MAC）と比較し，どのような応用に向いているかを明らかにする．
キーワード 無線センサネットワーク，ユビキタスコンピューティング，全ノードブロードキャスト，受信端
末始動通信，分散アルゴリズム

1. ま え が き

端末への情報周知を可能とするものであり，分散ネッ

小型無線端末の集団が基地局を介さずに自律的にている（例えば [2] を参照）．

トワークの一つの重要な基本要素であることが知られローカルな無線ネットワークを構築し，ユーザの要求

自律分散ネットワークとして，例えばユビキタスセンに応じたサービスを提供することが求められている

サネットワーク（USN）や Internet of Things（IoT）（比較的最近の例として [1] を参照）．この自律分散ネッ

においては，全ての端末が高性能であることは望めず，

トワークにおいて，端末（ノード）がデータパケット

バッテリーの制約が大きいなど性能の限られた低コスをその隣接端末全てに送信することをローカル（シントな端末を想定することが必須である．初期のユビキタ

グルホップ）ブロードキャストとよび，これを繰り返

スセンサネットワークの研究の多くは，Carrier Sense

し全端末にデータパケットを行きわたらせることを全

Multiple Access/Collision Avoidance（CSMA/CA）

ノード（マルチホップ）ブロードキャストとよぶ [2]．

に基づく Media Access Control（MAC）を採用してそして，この全ノードブロードキャストを実現する

いる．ところが，この CSMA/CA ベースの MAC を用

アルゴリズムをフラッディングプロトコルとよぶ．全いた小型無線端末（例えば Mica2Dot [3]）は，(1) 省

ノードブロードキャストは，端末間のルート構築や全電力性の点で問題があった．例えば，連続動作のもとでバッテリーが 4 時間ほどで切れてしまう実験結果も報†告されている [4]．また，(2) CSMA/CA を用いると，

電気通信大学，調布市
The University of Electro-Communications, Chofu-shi, 182–

全ノードブロードキャストにおいて隠れ端末問題 [2] が8585 Japan生じ，データパケットの到達率の低下が避けられない．

a) E-mail: m.nakagawa@uec.ac.jpb) E-mail: htanaka@uec.ac.jp

電子情報通信学会論文誌

すなわち，USN や IoT などのバッテリーの制約が大c 一般社団法人電子情報通信学会 2019
A Vol. J102–A No. 3 pp. 133–148 

133電子情報通信学会論文誌 2019/3 Vol. J102–A No. 3

きい近距離無線通信の端末を想定した全ノードブローの提案するアルゴリズムは，必ずしも無線通信環境に

ドキャストにおいては，以上の (1)，(2) の問題に配慮特化されるものではなく，分散アルゴリズムとしてもした新規なフラッディングプロトコルが必要である．

新規性をもつものと考えられる．

以上を踏まえ，本研究は間欠通信手法と受信端末始動通信 [5] を併用する非同期型フラッディングプロト

2. 関 連 研 究

コルを提案する．この間欠通信手法とは，端末の状態

本章では，提案手法の構成要素である，無線センサ

をデータパケットのやり取りを行うアクティブ状態とネットワークの間欠通信手法と受信端末始動通信の従通信にかかわる動作をしないスリープ状態の 2 状態

来研究について説明する．

を周期的に切り替え電力消費を節約するものであり，

2. 1 間欠通信手法の従来研究

duty-cycling [6] とも呼ばれている．一方，受信端末

間欠通信手法において，各端末は可能な限りスリー

始動通信は，CSMA/CA などのような従来の送信端

プ状態に移行することにより電力消費を抑える．し末始動通信とは逆に，受信予定端末が通信を始動し，かし一方で，各端末は通信を行うとき，通信相手端末

最終的に送信予定端末からのデータパケットを受信すとアクティブ状態のタイミングを合わせる必要がある手順を経る．

る．そのため，初期の代表的な間欠通信手法である

間欠通信手法と受信端末始動通信を併用するフラッ

S-MAC [10] では，各端末は間欠的に同期パケットのディングプロトコルは，受信端末始動通信に関する網やり取りを行うことで端末間の時刻を補正し，時刻の羅的なサーベイ論文 [7] によると，これまでに三つ提案

同期を維持している．しかしながら一定の同期精度をされている（それらの詳細は 2.2 で説明される）．とこ

維持するためには，データパケットの通信頻度と無関

ろが，これらの研究においては，ネットワークが定常係に同期パケットのやり取りが不可欠であり，そのた的であり，(1) 各端末がローカルなネットワーク情報をめのオーバーヘッドと，水晶発振器レベルの精度の高保持する，あるいは (2) 全端末があらかじめ間欠通信

い発振器が必要であった．

タイミングの同期を行う，などの強い前提がおかれて一方，精度の高い発振器を必要とせず，オーバーいた．これに対し，本研究は，上記の前提 (1)，(2) をヘッドの少ない手法として，データパケット通信の必

外したとき，間欠通信手法と受信端末始動通信のみに要に応じて通信タイミングを一時的に合わせる手法がよる必要最小限の構成により，全ノードブロードキャ

いくつも提案されている．図 1 に示す，この手法のストがどこまで可能であるか?という基本的問題に焦点

代表的な B-MAC [11] では，この一時的な同期のたを当てる．われわれの知る限り，またサーベイ論文 [7]めにデータパケットを送信する端末が，アクティブ状

によっても，このような基本的問題への取り組みは報態の一周期（図 1 の T (Wakeup period) に相当）の告されていない．更に，この必要最小限の提案手法を従来の代表的な送信端末始動通信の例（B-MAC）と比較し，この手法がどのような応用に向いているかを明らかにする．
本研究の構成は以下のとおりである．まず 2. では
関連する従来研究について説明し，提案手法との差異を明らかにする．3. では提案手法のアイデアを述べ，そのアルゴリズムの詳細を説明する．4. ではシミュレーションにより提案手法の長所と限界を明らかにする．5. では従来手法とのフェアな比較により提案手法の有用性を検証する．最後に 6. で本研究の結論と関連分野の課題について述べる．
本研究のアイデアの骨子は既に [8], [9] で公開されているが，本研究はそのアルゴリズムの詳細と必要なパラメータ設定，並びに系統的な性能評価をはじめて与え，関連研究との関係を明らかにする．なお，本研究134

図 1 送信端末始動 (B-MAC [11]) と受信端末始動(RI-MAC [5]) のタイムチャート
Fig. 1 Time charts for a sender-initiated scheme(B-MAC [11]) and a receiver-initiated scheme(RI-MAC [5]).

論文／受信端末始動通信による非同期型フラッディングプロトコルの提案とシミュレーション評価

長さの Long Preamble をデータパケットの前に付加

タパケットを返信する．隣接端末は存在通知パケット

して送信する．各端末は周期的にアクティブ状態とスの返信としてデータパケットを受信すると，データパ

リープ状態を繰り返すが，アクティブ状態時に一定期

ケットの受信が完了するまでアクティブ状態を延長し，間，通信に用いる周波数帯のモニタリング（Channel

受信完了後，受信完了報告（ACK）を返信する．

Sampling for Checking Channel Activity: CS）を

このように，受信端末始動の通信手法は，受信端末行う．データパケット送信要求の発生した送信予定によって送信端末の送信を管理することができる．し端末は，周波数帯の使用状況をモニタリング（Clear

たがって，一つの受信端末に対して複数の送信予定端

Channel Assessment: CCA）し，周辺にパケットの末が存在し，それらが互いに隠れ端末であっても，受送信を感知しない場合には，上記の Long Preamble

信端末側から，その一つを選択することによりデータを付加したデータパケットを送信する．モニタリング

パケットの衝突を回避することができる．受信端末始（CS）中に Long Preamble を受信した受信予定端末

動のパラダイムは送信端末始動と比べて新しく，現在は，データパケットを受信するまでアクティブ状態を延も研究が進んでいるが，既に幾つかの応用が得られて長する．この手法では，S-MAC のような大域的な同期いる [7]．例として，環境モニタリング [18]，空港旅客のオーバーヘッドが不要であり，低頻度の通信を行うの搭乗支援 [19]，スマートメータリングシステム [20]際に，S-MAC を上回る省電力性が得られている [11]．

や熱エネルギーハーベスティングのためのヒートコス

このようなデータパケット送信端末から通信を始動

トアロケータ [21] が知られている．

する（送信端末始動）手法として，同期パケットを連続受信端末始動のユニキャスト手法として，これまでに送信する関根・中村らの手法 [12] や，存在通知パケット

RI-MAC に加え，制御パケットの衝突確率を最小化す

を連続送信する X-MAC [13]，データパケットを連続るように間欠周期長を制御する IRDT [22], [23]，同期

送信する Speck-MAC [14]，更にトポロジーによってパケットによりあらかじめ端末間のゆるい同期状態を作使用手法を切り替える MiX-MAC [15] が提案されてり出す YA-EBS [24]，受信端末のウェイクアップ時刻

きた．これらの手法の中で，B-MAC と Speck-MAC

を正確に予測する RW-MAC [25] などが提案されていはローカルブロードキャストを繰り返すことにより，る．これらの手法の中で，全ノードブロードキャストを

全ノードブロードキャストを行うことが，原理的には行うために拡張されたものとして，RI-MAC の拡張で可能である．しかし，これらの手法では，マルチホッ

ある ADB [26]，BW-MAC の拡張である RWB [27]，プ環境で複数同時の送信端末が生じる際に発生する隠YA-EBS の拡張である YA-MAC [28] がある．

れ端末問題を回避することは困難である（その詳細は5.2 のシミュレーションにより明らかになる）．

ADB は初期に開発された代表的な受信端末始動のフラッディングプロトコルであり，端末をかなり密に

2. 2 受信端末始動通信の従来研究分布させた場合でも，データパケット到達率 100%を

RICER [16], [17] は，上記とは異なるアプローチで達成することが報告されている [26]．この優れた結果

間欠通信による省電力な通信手法を提案している．上の主な要因は，(1) 使用されているユニキャスト手法

記の手法 [11]〜[15] が，データパケット送信予定端末

RI-MAC のランダムなバックオフによる衝突回復機から隣接端末への働きかけにより通信を始動する手法

構 [26, p.48] と，(2) 各端末が全ての隣接端末の存在であるのに対し，[16], [17] は，隣接端末（データパケッ

情報と，そこへのリンク品質情報を常に保持し，更にト受信予定端末）からの働きかけにより始動するとい第 2 隣接端末の存在情報をも保持する [26, p.49] ことう点が異なる．図 1 に，この受信端末始動のパラダによる．この隣接端末の存在情報とそのリンク品質情

イムを広く普及した RI-MAC [5] の最もシンプルなタ

報により各端末はデータパケット送信委任，すなわちイムチャートを示す．RI-MAC において，通常，端末

リンク品質が悪い端末へのデータパケット送信は行わは周期的にアクティブ状態となり，存在通知パケットず，より良いリンク品質をもつ端末にデータパケット（Wakeup Beacon: WB）の送信と周波数帯のモニタの送信を任せることが可能となる．

リング（monitoring）を行っている．データパケット

一方，RWB は一つの端末の通信可能範囲に四つ程

送信予定端末（sender）は，隣接端末（receiver）か

度の端末が存在する密過ぎないネットワークであれば，らの存在通知パケットを受信するためにモニタリング

X-MAC と同等の送信端末始動通信と比べて，消費電を行い，この間に存在通知パケットを受信するとデー

力が約 35%に抑えられ，かつ高いデータパケット到達135電子情報通信学会論文誌 2019/3 Vol. J102–A No. 3

率 (約 100%) を達成することが報告されている [27]．

てのパケット（制御パケット及びデータパケット）はこの優れた結果の主な要因は，(1) 使用されているユ単一の周波数帯域で送信されるものとする．

ニキャスト手法 RW-MAC のウェイクアップ時刻を正確に予測する機構と，(2) 各端末が隣接端末の存在情報等を常に維持し，適切に全ノードブロードキャスト
を停止する機構を含むことによる．なお，YA-MAC
は，以上の ADB，RWB と同様に優れた結果を得ているが，その主な要因は，各端末が全ての隣接端末の3. 2 提案手法のアルゴリズム
以下では，提案手法の動作アルゴリズムをステップ

1，2，3，4 の 4 段階に分けて説明する．
(1) データパケットの送信予約と送信予定端末間の競合回避（ステップ 1）
動作アルゴリズムの説明のため，一般性を失わない

存在情報を維持し，更に (3) 端末間の間欠動作のタイ

最小限の構成として図 2 に示す例を考える．ここでミングをゆるく同期していることによる．

は，各端末は○で示され，その通信可能範囲は破線で要するに，ADB や RWB，YA-MAC が目的通り示した端末を中心とする一定範囲内とする．端末は，に動作するためには，ネットワークが定常的であり，それぞれ独自のローカルタイミング（各端末が管理す(1) 各端末がローカルなネットワーク情報（トポロジー，る時刻）を基に動作し，このローカルタイミングを基

リンク品質）を保持する，あるいは (2) 全端末があらかに (i) 周期的にアクティブ状態とスリープ状態を切り

じめ間欠通信タイミングの同期を行う，という強い前提替える通常モード，(ii) 送信予定のデータパケットをが必要である．次章では上記の (1)，(2) の前提を必要と保持する送信モード，(iii) データパケットの受信予定

しない，新規なフラッディングプロトコルを提案する．

のある受信モード，の 3 状態のいずれかをとる．

3. 新規なフラッディングプロトコルの提案

一般に，データパケットの送信要求はネットワーク
内に同時に複数箇所で生じ得るので，ここではデータ

本章では，間欠通信手法と受信端末始動通信を併用

パケット送信予定端末 S，B の二つが存在するものとするフラッディングプロトコルのアイデアを述べ，そ仮定する．また送信予定端末に対し，その隣接端末もの詳細の説明を例に基づいて与える．

一般に複数存在し得るので，送信予定端末 S，B に対

3. 1 概要し，その隣接端末をそれぞれ端末 A，D と設定する．

以下に，(1) ローカルなネットワーク情報（トポロ

提案手法の衝突回避アルゴリズムを示すため，端末 A

ジー，リンク品質）を必要とせず，更に (2) 端末間のに隣接し，送信予定端末 S，B の通信可能範囲外にあ同期のためのオーバーヘッドも必要としない，新規なる隠れ端末 C の存在も仮定する．

フラッディングプロトコルを提案する．

データパケットの送信要求が生じてから，そのデー

提案手法のアイデアは，次の二つの要素 (i)，(ii) か

タパケットの送受信が完了するまでのタイムチャート

ら構成されている．(i) データパケット送信予定端末は，を図 3 に示す．図 3 の例では，当初，端末 S，B が同期パケットを用いない間欠通信により，ローカルブ

送信モード，端末 D，A，C が通常モードである．以

ロードキャストの対象となる隣接端末を発見し，その下，ステップ 1 における制御パケットの詳しいやりと

送信予約を行う．(ii) (i) の結果，データパケット受信予定となった端末は，その隣接端末に対しデータパケッ
トとの衝突を回避するための通知をあらかじめ行う．
これら (i)，(ii) の要素を実現するため，各端末は固有の ID をもち，存在通知（Wakeup Beacon: WB），送信予約（Request To Send: RTS）
，送信権通知（Clear

To Send: CTS），スリープ命令［CTS(sleep)］の 4種類の制御パケットを送信できるものとする（注 1）．全

（注 1）
：本研究は，1. で述べたように必要最小限の構成での性能評価を目的とするため，（ACK のような）受信確認を行わないものとした．これにより，制御パケットの送信回数が減り，パケットの衝突頻度の低減が期待できる．なお，提案手法 [9] に含まれる範囲で，受信確認の手続
きを含めることも可能である．

136

図 2 ネットワーク例
Fig. 2 Example of topology.

論文／受信端末始動通信による非同期型フラッディングプロトコルの提案とシミュレーション評価

図5

図3

提案手法のデータパケット送信要求発生後のタイムチャート．図中の T と Ta はそれぞれ間欠周期長（1 周期）とアクティブ状態である期間（アクティブ期間）の長さを表す．
Fig. 3 Time chart after the data packet transmission
request in the proposed scheme. T and Ta
in the ﬁgure represent the intermittent cycle
length (one cycle) and the active state period(active period), respectively.

ステップ 1 における送信権通知パケット（CTS）の返信
Fig. 5 Reply of Clear To Send (CTS) packet in
Step 1.

定端末のその時点でのローカルタイミングとデータパケット送信開始タイミング並びに送信終了タイミングが含まれるものとする．これにより送信予約パケット（RTS）を受け取った端末は，そのローカルタイミング
を送信予定端末に追従させ，データパケット送信終了
タイミングを知ることができる（すなわち，送信予定
端末とのアクティブスケジュールの一時的な同期（ハンドシェイク）が達成される）．なお，このようなパケットの返信の際，提案手法ではランダムなバックオ
フ時間を設定し，確率的に返信パケット同士の衝突を回避している（図 3 の存在通知パケット（WB）送信

図 4

ステップ 1 における送信予約パケット（RTS）の返信
Fig. 4 Reply of Request To Send (RTS) packet in
Step 1.

りを説明する．送信モードである端末 S，B は，1 周期（図 3 の T に相当する長さ）にわたりアクティブ状態を維持し，その間にアクティブ状態である周辺端末（通信可能範囲内にある端末）からの存在通知パケッ
ト（WB）を全て拾い，送信予約パケット（RTS）を）4）．なお，存在通知パケット（WB）
返信する（注 2（図には，端末がデータパケットを受信したことがあるかの情報が含まれており，送信予約パケット（RTS）は，一度データパケットを受信した端末には返信されない．ここで，送信予約パケット（RTS）には，送信予（注 2）：本研究では，受信確認を行わないものとしたため，端末 S は，
送信予約パケット（RTS）を返信した時点で，通信が成功したものと仮定する．したがって，もし送信予約パケット（RTS）が他の制御パケットと衝突しても，端末 S はそのことを認識できず，その後，受信相手がいないままデータパケットの送信を行うことになる．このような事態がデータパケット到達率に与える影響は，最大バックオフ時間が小さい場
合には大きいものの，最大バックオフ時間がある程度大きい場合には無視できる（4.3(2) 及び図 10 (b) 参照）．

後の幾つかの小さな時間スロットが選択可能なバック
オフ時間を表している）．このバックオフ時間の最大値（最大バックオフ時間）は，通常モードである端末がア
クティブ状態を維持する時間（アクティブ期間，図 3の Ta で表す長さに相当）より短いように設定する．
最大バックオフ時間内に複数の送信予約パケット（RTS）を受信した端末は，そのうち 1 台を選び，送信権通知パケット（CTS）を返信することで送信予定端
末間の競合を回避する．送信権通知パケット（CTS）
は，最大バックオフ時間の経過後からアクティブ期間の終了までに送信される．図 3 の例では，端末 D が送
信予定端末 S，B から送信予約パケット（RTS）を受
信し，送信予定端末 S からの送信予約を優先し，送信権通知パケット（CTS）（送信予定端末 B にとってはスリープ命令パケット［CTS(sleep)］）を返信している（図 5）．スリープ状態となった送信予定端末 B は，
データパケットの送信を見送った回数を送信見送り回
数として保存しておく．なお，スリープ命令パケット［CTS(sleep)］にも，送信予約パケット（RTS）と同様のタイミング情報（送信予定端末のその時点でのローカルタイミングとデータパケット送信開始タイミ
137電子情報通信学会論文誌 2019/3 Vol. J102–A No. 3

ング並びに送信終了タイミング）が含まれ，スリープ状態を継続する時間は一定ではなく，このタイミング
情報によって決定される．
送信予約パケット（RTS）を複数受信した端末が送信予定端末を選ぶ際の優先順位は，送信見送り回数が多いものほど高くなるように設定しておく．これにより，ある送信予定端末が永久に選択されないような事
態は回避される．送信見送り回数が送信予定端末間で等しい場合は，データパケット送信開始タイミングが早い端末が優先される（注 3）．送信見送り回数がある一定数（最大送信見送り回数）を超えた場合，その送信予

図 6 ステップ 2 におけるスリープ命令パケット［CTS(sleep)］の返信
Fig. 6 Reply to Sleep command packet [CTS(sleep)]in Step 2.

定端末はデータパケットの送信を諦め，保持していた
データパケットを破棄し（注 4），通常モードに移行する．
以上のステップ 1 の手順により，複数の送信予定端
末が存在する場合でも，選ばれた送信予定端末以外がスリープ状態となることで，データパケット同士の衝突が回避される．

(2) データパケット受信予定端末による衝突回避（ステップ 2）ステップ 2 では，存在通知パケット（WB）などの図 7 ステップ 3 におけるデータパケットの送信
Fig. 7 Transmission of data packet in Step 3.

制御パケットとデータパケットとの衝突回避のための動作を行う．

なお，スリープ命令パケット［CTS(sleep)］には受信

上記のステップ 1 において送信予約パケット（RTS）

予定端末の予約先（すなわち，ハンドシェイクした送を受信した端末は，ステップ 2 において受信モード

信予定端末の ID）の情報も含まれているとし，予約へ移行する．受信モードに移行した端末は，一定期間先が同じである受信モードの端末がこのスリープ命令（データパケットの受信に要する時間，若しくは 1 周

パケット［CTS(sleep)］を受信しても，スリープ状態期間）モニタリングを行い，その間受信した存在通知とはならないものとする．

パケット（WB）などの制御パケットに対しスリープ

以上のステップ 2 の手順により，受信モードとなっ命令パケット［CTS(sleep)］を返信する．なお，本研た端末は，あらかじめその隣接端末で衝突の原因とな究では，受信モードとなった端末のモニタリング時間

る可能性があるものをスリープ状態として，確実なを 1 周期（図 3 の T に相当する長さ）と設定する．

データパケットの受信に備える．

図 3 の例では，ステップ 2 において受信モードとなっ(3) データパケットの送受信（ステップ 3）

た受信予定端末 A が，通常モードの端末 C からの存

以上のステップ 1，2 の後に送信予定端末 S と受信

在通知パケット（WB）に対しスリープ命令パケット予定端末 A，D の間でデータパケットの送受信が行わ［CTS(sleep)］を返信している．これにより通常モードれる（図 7）．データパケットの送受信を完了した端の端末 C を受信予定端末 A のデータパケットの受信完

末 S，A，D はその後スリープ状態に移行し，ステッ）了までスリープ状態とさせることができる（注 5（図6）．

プ 3 の期間（1 周期，図 3 の T に相当する長さ）の終了までスリープ状態を維持する．また，データパケッ（注 3）：万が一，データパケット送信開始タイミングも等しい場合は，ID の小さい端末が優先される．
：端末の記憶容量が限られており，複数のデータパケットを同時（注 4）に記憶できないことを考慮した．
：この制御に限らず，提案手法には，セキュリティ面で問題のあ（注 5）る制御が含まれている．しかしながら，本研究は，必要最小限の構成での性能評価を目的とするため，セキュリティ面の考慮は行わなかった．
一方で，セキュリティ面の考慮は，想定する用途によっては重要な要素であるので，興味深い課題の一つである．

138

トの送信予定をキャンセルした端末 B 及び，スリープ状態であった隣接端末 C も，ステップ 3 の期間終了までスリープ状態を維持する．なお，データパケットの送信を完了したデータパケット送信端末は，データパケットの送信終了後もデータパケットを保持し続け，データパケットを受信できなかった端末の救済（ステッ論文／受信端末始動通信による非同期型フラッディングプロトコルの提案とシミュレーション評価

プ 4）に備える．

(4) データパケットの送受信終了後の動作（ステッストに要する時間，(3) 全端末の消費電力量，をシミュ
レーションにより求める．本研究では全ノードブロー
ドキャストの終了判定条件を次のように定義する（注 7）．

プ 4）
データパケットの送受信終了後の動作は，基本的にすなわち，(i) 全ての端末が過去にデータパケットをステップ 1，2，3 の繰り返しとなる．ただし，一度所持したことがある，あるいは (ii) データパケットを

データパケットを送信した端末は，ステップ 1 におい

保持している端末が存在しなくなった（注 8），あるいはて，1 周期よりも短い期間（データパケット送信後モ(iii) あらかじめ設定したタイムアウト時間になった

ニタリング時間）の間だけモニタリングを行う（一度（本研究では一律 10000 秒と設定する）．

データパケットを送信した端末のステップ 1 を，通常以上の (1) のデータパケット到達率とは，全ノードのステップ 1 と区別するために，これを便宜上ステッ

ブロードキャスト終了時までに，（全ノードブロード

プ 4 と呼ぶ）．これは間欠周期長が大きい場合にモニキャスト開始端末を除く）全端末に対し，データパケッ

タリングによる電力消費を低く抑えるためである．

トを正しく受信した端末の割合のことである．また，

図 3 の例で説明する．データパケットの送信を完了(2) の全ノードブロードキャストに要する時間とは，全した端末 S は，ステップ 3 の期間終了後，スリープ状

ノードブロードキャスト開始端末にデータパケットの態から送信モードに移行し，上記で説明したステップ

送信要求が生じてから全端末にデータパケットが行き

4 の動作を行う．一方，データパケットをまだ一度も送渡るまでの時間のことである．更に，(3) の全端末の信したことのない端末 A，D は，通常のステップ 1 の消費電力量とは，全ノードブロードキャストに要する動作を行う．なお，データパケットの送信予定をキャ

時間の間に，各端末が送信状態，受信状態，モニタリンセルした端末 B 及び，スリープ状態であった隣接端ング状態であった時間から計算された消費電力量の総末 C は，ステップ 3 の期間終了後，それぞれ送信モー和のことである．

ド及び通常モードに移行し，ステップ 1，2，3 を繰り返す．

消費電力量の評価にあたり，端末の送信状態，受信状態，モニタリング状態の（単位時間（秒）あたりの）以上の全ての動作（ステップ 1，2，3，及びステッ

消費電力値をそれぞれ次のように算出する．まず，送プ 4）は，あらかじめ設定したタイムアウト時間まで

受信時の消費電力値を，RICER で想定されている端繰り返される．

末での値 [16, p.3772] に設定する（したがって，送信，

4. シミュレーションによる提案手法の性能評価．一方，モニタリング
受信時の消費電力値の比が 2 : 1）時の消費電力値は，近年の研究動向 [29], [30] によると，

RICER で想定されている送受信時の値（数 mW）の本章では，3. で提案したフラッディングプロトコル

数百分の 1 程度（数十 µW）まで低減が可能になってを現実的な通信環境の設定のもとで動作させ，その性いる．これらを踏まえ，本研究では RICER で想定さ能の特性と限界を明らかにする．

れている端末での値 [16, p.3772] を基本に，送信，受

4. 1 シミュレーションモデル

信，モニタリング時の消費電力値の比を 200 : 100 : 1

提案手法による全ノードブロードキャストの性能となるように設定する（表 1 参照）．

を評価するため，格子状に配置した場合における（注 6）

シミュレーションの諸元を表 1 に示す．4. におい(1) データパケット到達率，(2) 全ノードブロードキャて特に記載がないパラメータは表 1 に従うものとす（注 6）：本研究では，格子状配置のみを扱うが，隣接端末数に偏りのある配置（例えば，スター型やツリー型のトポロジーをもつ配置）の場合，送信端末間で送信権の獲得のしやすさに本質的な差が生じる．これにより，電池の消耗が極端に早い端末が生じ，全ノードブロードキャストの途中で電池切れを起こす可能性がある．しかしながら，このことは，以下の理由により，提案手法による全ノードブロードキャストの障害とはならない．(1) 提案手法は，定常的なネットワークトポロジーを前提としない．(2) 提案手法は，端末間の同期を必要としない．したがって，
たとえ，ある端末が電池切れを起こしたとしても，別のルートからデー
タパケットの伝搬が可能であり，全ノードブロードキャストの継続が可能である．また，電池切れの端末の交換も，任意の時間に，任意の場所で可能である．

る．∗ 印の付いている項目は本章のシミュレーションにおいて常に一定に設定されるものである．以下のシ（注 7）：この終了判定条件は，シミュレーションプログラムが（俯瞰的な立場から）全ノードブロードキャストが終了したかどうかを判定するためのものである．各端末が，全ノードブロードキャストの終了を判定する訳ではない．
：データパケットを保持する端末は，送信見送り回数が最大値を（注 8）超えると，保持しているデータパケットを破棄する．これにより，デー
タパケットを保持している端末がネットワークから存在しなくなる可能性がある．実際には，このようなことはほとんど起こらないが，未定義な状況を作らないために，終了条件 (ii) を設けている．

139

電子情報通信学会論文誌 2019/3 Vol. J102–A No. 3
表 1 シミュレーション設定
Table 1 Simulation speciﬁcation.
端末の最小時間刻み幅 (1slot)
0.001 秒∗
通信速度
60kbps∗
制御パケット長(WB, RTS, CTS, CTS(sleep)) 60bit (送信時間 1slot)∗
データパケット長 (DATA)
6kbit (送信時間 100slot)∗
間欠周期長 (T )1 秒 (1000slot)
最大送信見送り回数 (Max. Post.) 0〜3 回
アクティブ期間 (Ta )0.015 秒 (15slot)∗
最大バックオフ時間
5slot
データパケット送信後
モニタリング時間
0.5 秒 (500slot)
端末数
121∗
端末の配置
11 × 11 格子状配置∗
全ノードブロードキャスト
開始端末
4 隅の内の 1 端末∗
通信可能半径(単位：最隣接端末間距離)1
試行回数10000 回∗
端末の送信電力4mW∗
端末の受信電力2mW∗
端末のモニタリング電力
0.02mW∗

ミュレーションは，Java によるプログラムを自作し

図8

端末の格子状配置における各端末ごとの平均データ
パケット到達率．最大送信見送り回数（Max. Post.）
は (a) 0 回，(b) 1 回，(c) 2 回，(d) 3 回である．
Fig. 8 Average data packet delivery ratio for eachnode in lattice arrangement. Each Maximum
Postponement Number (Max. Post.) is (a) 0,(b) 1, (c) 2, (d) 3, respectively.

行った．これらのプログラムは次の URL [31] で公開されている．なお，理論値の得られている場合の種々

送り回数（Maximum Postponement Number: Max.

のケースで理論値とシミュレーション結果の比較を行

Post.）を変化させたときの各種性能を明らかにする．

いプログラムの信頼性を確認しており，その範囲で問題は認められない．
各端末の性能は同一とし，各端末の刻む時間の最小シミュレーション設定は，最大送信見送り回数を，

0，1，2，3 の 4 通りに設定し，その他の設定は表 1に従うものとした．

単位（最小時間刻み幅）は 1slot で，簡単のためその図 8 は，全ノードブロードキャスト開始端末を左上

slot の頭は端末間で揃っているものとする（注 9）．また，隅の端末とし，10000 回の試行結果を各端末ごとに平各端末は互いに非同期状態で動作するものとし，各試均したデータパケット到達率を示している（すなわち，行ごとに端末のローカルタイミングをランダムに設定

10000 回の試行に対して，各端末ごとにデータパケッ

している．更に，各端末は，各試行ごとに重複のない

トを正しく受信できた試行の割合を示している）．各

ランダムな番号を ID として付与される．全ノードブ○が端末を表しており，色の濃淡が平均データパケッ

ロードキャストは，4 隅の内の 1 端末から開始される

ト到達率の値を表している．カラーバーの下限値は，ものとし，1 種類のデータパケットを全体に行き渡ら

各端末の平均データパケット到達率の最低値に合わせせることを想定する．通信の失敗はパケット同士の衝てある．図 8 (b)，(c)，(d) より，最大送信見送り回

突のみにより発生するものとする．なお，シミュレー

数が 1 以上の場合では，ネットワークの隅の端末へのションの開始時，上記の全ノードブロードキャスト開

データパケット到達率が比較的低下しているものの，始端末は送信モードであるとし，それ以外の端末は通全ての端末で 98%以上のデータパケット到達率が得ら常モードであるとした．

れていることが分かる．また，図 8 (a) の最大送信見4. 2 端末の格子状配置における各種性能の評価

送り回数の設定が 0 という厳しい条件下であっても，本節では，提案手法の最も基本的な性能評価を与全端末で 90%を上回るデータパケット到達率が得られえる．すなわち，提案手法のデータパケット到達率に最も大きな影響を与えると考えられる最大送信見（注 9）：仮に slot の頭がいくらかずれていても 1slot 長が充分短いため，提案手法の動作に影響はない．

140

ている．
次に，図 9 に，10000 回の試行結果から得られた(a) データパケット到達率，(b) 全ノードブロードキャ
ストに要する時間，(c) 全端末の消費電力量のヒストグ

論文／受信端末始動通信による非同期型フラッディングプロトコルの提案とシミュレーション評価

及び全端末の消費電力量は最大送信見送り回数に対して大きく依存しないことが分かる（すなわち，これらのヒストグラムはほぼ同一となっている）．しかしながら，図 9 (b)，(c) の拡大図（Enlarged view）より，
最大送信見送り回数が大きいほど，全ノードブロード
キャストに要する時間と消費電力量はわずかながら大きくなることが分かる．
以上より，最大送信見送り回数を 1 以上に設定する
ことで，ほぼ確実に高いデータパケット到達率が得られることが分かった．また，最大送信見送り回数が 2以上では，全ノードブロードキャストに要する時間や全端末の消費電力量がわずかながら大きくなることか
ら，必要以上に大きな最大送信見送り回数を設定する
メリットはないことが分かった．

4. 3 さまざまな条件下におけるデータパケット到
達率
本節では，平均データパケット到達率に的を絞り，さまざまな条件下における提案手法の特性を明らかにする．ここで平均データパケット到達率とは，10000
回の試行結果から得られたデータパケット到達率（すなわち，全ノードブロードキャスト開始端末を除く全端末に対し，データパケットを正しく受信した端末の割合）の平均のことである．

(1) データパケット到達率の通信可能半径依存性の検討
図 9 最大送信見送り回数（Max. Post.）が 0，1，2，3 のそれぞれでの各種性能を表すヒストグラム．(a) デー
タパケット到達率，(b) 全ノードブロードキャストに要する時間，(c) 全端末の消費電力量
Fig. 9 Histograms showing various performances ineach case of Maximum Postponement Number (Max. Post.) 0, 1, 2, and 3, respectively.
(a) Data packet delivery ratio, (b) End-to-end
delay, (c) Total power consumption.

前節の結果では，全ノードブロードキャスト開始端末からのホップ数に伴いデータパケット到達率が低下する傾向が見られた．そこで，(1) では格子状配置における各端末間の距離を小さくすることで，通信可能範囲に存在する端末数を増やし，より少ないホップ数
で全ノードブロードキャスト可能な環境でシミュレー
ションを行った．なお，通信可能範囲とは通信可能半径（Communication Radius）をもつ円の内側を指し，ラムを示す．まず，(a) データパケット到達率に関し，

本研究では通信可能半径の単位として格子状配置にお図 9 (a) より，最大送信見送り回数が 1 以上の場合は，ける最も隣接した端末間の距離（最隣接端末間距離）99%以上のデータパケット到達率がほぼ確実に得られを用いる．

ることが分かる．また，図 9 (a) の拡大図（Enlarged

シミュレーション設定は，通信可能半径を 1，2，3，

view）より，最大送信見送り回数が 1 の場合と 2 以上

4（すなわち，通信可能範囲内の端末数を 4，12，28，の場合を比べると，最大送信見送り回数が 2 以上の場48）とする以外は表 1 に従うものとした．

合の方がより確実に 99%以上のデータパケット到達率

シミュレーション結果を図 10 (a) に示す．図は，横が得られることが分かる．次に (b) 全ノードブロード

軸を通信可能半径とし，縦軸を平均データパケット到

キャストに要する時間と (c) 全端末の消費電力量に関達率としたものである．平均データパケット到達率は，し，図 9 (b)，(c) より，最大送信見送り回数が 1 以上

最大送信見送り回数（Max. Post.）が 0，1，2，3 のその場合では，全ノードブロードキャストに要する時間

れぞれに対して示してある．最大送信見送り回数が 0141電子情報通信学会論文誌 2019/3 Vol. J102–A No. 3(2) データパケット到達率の最大バックオフ時間依存性の検討(1) では提案手法が失敗する原因が各種パケットの衝突であることを明らかにした．そこで (2) では，各種パケットの衝突の中でも返信パケット同士（送信予約パケット（RTS）やスリープ命令パケット［CTS(sleep)］）の衝突回避のために設定している最大バックオフ時間とデータパケット到達率の関係を明らかにする．
シミュレーション設定は，通信可能半径を 1，2，3，

4，最大送信見送り回数を 0，最大バックオフ時間を任意とする以外は表 1 に従うものとした．最大送信見送
り回数は，最大バックオフ時間依存性を明瞭に示すた
図 10

さまざまな条件下における平均データパケット到達率．(a) 通信可能半径依存性，(b) 最大バックオ
フ時間依存性，(c) データパケット送信後モニタリ
ング時間依存性，(d) 間欠周期長依存性．図中のMax. Post. は最大送信見送り回数を表す．
Fig. 10 Average data packet delivery ratios undervarious conditions. (a) Communication radius dependency, (b) Maximum backoﬀ timedependency, (c) Monitoring time (after data
packet transmission) dependency, (d) Intermittent cycle length dependency.

め，あえて厳しい 0 と設定した（1 以上に設定しても依存性の傾向に変わりはないことが認められる）．
シミュレーション結果を図 10 (b) に示す．図は，横軸を最大バックオフ時間とし，縦軸を平均データパケッ
ト到達率としたものである．平均データパケット到達率は，通信可能半径（Commun. Radius）が 1，2，3，

4 のそれぞれに対して示してある．いずれの通信可能半径においても，最大バックオフ時間を増加させると，（上昇率は徐々に低下するものの）データパケット到の場合，通信可能半径が 2 においてデータパケット到

達率が上昇し，ある程度に達すると，ほぼ頭打ちにな

達率が極大になり，それ以上では通信可能半径の拡大

ることが分かる．データパケット到達率が最大バックに伴いデータパケット到達率が低下するという結果がオフ時間の増加に伴い上昇する要因は，最大バックオ得られた．また，図 10 (a) の拡大図（Enlarged view）

フ時間の増加に伴い，返信パケット同士の衝突の確率より，最大送信見送り回数が 2 以上の場合も，通信可が低減され，返信パケットの送受信の成功率が上昇す

能半径が 2 においてデータパケット到達率が極大になるためである（注 10）．一方で，最大バックオフ時間はアることが分かる．なお，最大送信見送り回数が 1 の場

クティブ期間の下限を決めており，最大バックオフ時

合には，例外的に通信可能半径が 1 においてデータパ間を極端に大きくすることは，アクティブ期間の延長

ケット到達率が極大になる．通信可能半径が 2 以上のに繋がり，高い省電力効果が期待できなくなる．した

場合にデータパケット到達率が低下する主な要因は，がって，最大バックオフ時間は必要以上に大きく設定

通信可能半径の拡大に伴い，各種パケット（制御パケッ

するメリットはない．以降では，最も厳しい環境であト及びデータパケット）の衝突率が上昇するためである通信可能半径が 4 の場合にデータパケット到達率がる．一方，通信可能半径が 1 の場合に（一部の例外をほとんど上昇しなくなる 8slot 付近に最大バックオフ

除き）データパケット到達率が低下する主な要因は，時間を設定する．

各種パケットの衝突率は低下するものの，データパケット送信後モニタリング時間におけるデータパケッ(3) データパケット到達率のデータパケット送信後
モニタリング時間依存性の検討

ト未受信端末の救済機会が減少するためと考えられる．

提案手法では，データパケット送信終了後の周期的以上より，提案手法では，データパケット到達率がなモニタリング（データパケット送信後モニタリング）

ある通信可能半径において極大になることが分かった．
ただし，現実的には最大送信見送り回数を 1 以上の値に設定することにより，いずれの通信可能半径においても十分高いデータパケット到達率を得ることができる．
142（注 10）：例えば，送信予約パケット（RTS）同士の衝突の確率を低減する
ことにより，受信相手がいないままデータパケットを送信してしまう事態を低減することができる．同様に，スリープ命令パケット［CTS(sleep)］同士の衝突の確率を低減することにより，データパケットと存在通知パケットが衝突してしまう事態を低減することができる．

論文／受信端末始動通信による非同期型フラッディングプロトコルの提案とシミュレーション評価の電力消費を低く抑えるために，データパケット送信外は表 1 に従うものとした．通信可能半径は 3 以下に後モニタリング時間を 1 周期よりも短く設定する．し設定しても依存性の傾向に変わりはないことが認めらかしながら，このデータパケット送信後モニタリン

れる．

グ時間を小さく設定し過ぎると，データパケットを受シミュレーション結果を図 10 (d) に示す．図は，横信できなかった端末の救済の機会が減少し，データパ

軸を間欠周期長とし，縦軸を平均データパケット到達

ケット到達率の低下に繋がる恐れがある．そこで (3)率としたものである．平均データパケット到達率は，ではデータパケット送信後モニタリング時間とデータ

最大送信見送り回数（Max. Post.）が 0，1，2，3 のパケット到達率の関係を明らかにする．

それぞれに対して示してある．最大送信見送り回数がシミュレーション設定は，通信可能半径を 4，最大0 の場合では，10 秒以下の比較的短い間欠周期長にバックオフ時間を 8slot，データパケット送信後モニ

おいて，間欠周期長の減少に伴いデータパケット到達

タリング時間を任意とする以外は表 1 に従うものとし率が低下していることが分かる．しかし，最大送信見た．通信可能半径は 3 以下に設定しても依存性の傾向

送り回数を 1 以上に設定することにより，比較的短いに変わりはないことが認められる．

間欠周期長に対してもデータパケット到達率の低下をシミュレーション結果を図 10 (c) に示す．図は，横大きく抑えられることが分かる．以上より，最大送信軸をデータパケット送信後モニタリング時間とし，縦見送り回数を 1 以上に設定することで，データパケッ

軸を平均データパケット到達率としたものである．平均

ト到達率を低下させることなく，目的とする応用に応

データパケット到達率は，最大送信見送り回数（Max.

じて間欠周期長を任意の大きさに設定できることが分

Post.）が 0，1，2，3 のそれぞれに対して示してある．

かった．

最大送信見送り回数が 0 の場合では，データパケット
送信後モニタリング時間が 500slot において，データ

5. 従来手法との性能比較

パケット到達率が極大になり，それ以下ではデータパ

本章では，提案手法のアルゴリズムの有用性を検証

ケット送信後モニタリング時間の減少に伴い，データするために，受信端末始動である提案手法と，従来のパケット到達率も低下していることが分かる．一方，

送信端末始動の代表的手法（B-MAC）の性能を比較

最大送信見送り回数が 1 以上の場合は，データパケッ

する．

ト送信後モニタリング時間の減少に伴うデータパケッ

5. 1 シミュレーションモデル

ト到達率の低下を大きく抑えられることが分かる．し

提案手法の基本動作は 4. までと同様とする．比較

かしながら，最大送信見送り回数が 1 以上であっても，する対象は送信端末始動の B-MAC を用いた全ノード

データパケット送信後モニタリング時間の減少に伴うブロードキャストとする．B-MAC の基本動作は図 1

データパケット到達率の低下はわずかながら認められに従うものとし，周期的なモニタリング（CS）の長さ

る．以降では，省電力性と高いデータパケット到達率

及び Long Preamble 送信前の周波数帯のモニタリンを両立させるため，最大送信見送り回数が 0 の場合

グ（CCA）時間を 1slot とした [11]．今回プリアンブにデータパケット到達率が最大となる 500slot 付近にルによる送信先の指定は行わないものとする．これにデータパケット送信後モニタリング時間を設定する．

より送信端末からプリアンブルを受信した端末全てに(4) データパケット到達率の間欠周期長依存性のデータパケットがローカルブロードキャストされる．

検討

各端末の性能は一律とし，各端末の刻む時間の最小

大きな間欠周期長は，間欠周期長に対するアクティ

単位（最小時間刻み幅）は 1slot で，その 1slot の頭は

ブ期間のデューティ比を下げることができる（したがっ端末間で揃っているものとする．各端末は互いに非同て，省電力効果を期待することができる）．しかし，間期状態で動作するものとし，各試行ごとに端末のロー

欠周期長を設定する上で，データパケット到達率に与カルタイミングをランダムに設定している．また，各える影響は自明ではなく，事前に調べておく必要があ

端末は，各試行ごとに重複のないランダムな番号を IDる．そこで (4) では間欠周期長とデータパケット到達として付与される．シミュレーションは，121 台の端末率の関係を明らかにする．

を等間隔に 11 × 11 の格子状に配置し，ネットワーク

シミュレーション設定は，通信可能半径を 4，最大の中心に位置する一つの端末から全体へデータパケッ

バックオフ時間を 8slot，間欠周期長を任意とする以トを全ノードブロードキャストさせることを想定して
143

電子情報通信学会論文誌 2019/3 Vol. J102–A No. 3
表 2 シミュレーション設定
Table 2 Simulation speciﬁcation.
端末の最小時間刻み幅 (1slot)
0.001 秒∗
通信速度
60kbps∗
制御パケット長(WB, RTS, CTS, CTS(sleep)) 60bit (送信時間 1slot)∗
データパケット長 (DATA)
6kbit (送信時間 100slot)∗
間欠周期長 (T )1 秒 (1000slot)∗
最大送信見送り回数 (Max. Post.) 0〜2 回
アクティブ期間 (Ta )(提案手法)
0.015 秒 (15slot)∗
最大バックオフ時間 (提案手法)
8slot∗
データパケット送信後
モニタリング時間 (提案手法)
0.5 秒 (500slot)∗
CS, CCA 長 (B-MAC)
0.001 秒 (1slot)∗
Long Preamble (B-MAC)
1 秒 (1000slot)∗
端末数
121∗
端末の配置
11 × 11 格子状配置∗
全ノードブロードキャスト
開始端末
中心の 1 端末∗
通信可能半径(単位：最隣接端末間距離)2
試行回数10000 回 ∗端末の送信電力4mW∗
端末の受信電力2mW∗
端末のモニタリング電力
0.02mW∗

図 12

端末の格子状配置における各端末ごとの平均データ
パケット到達率の比較．(a)(b) B-MAC, (c)(d) 提案手法．図中の CR は通信可能半径，DL はデータ
パケット長を表す．最大送信見送り回数は全て 1．
Fig. 12 Comparison of average data packet delivery
ratios for each node in lattice arrangement.
(a)(b) B-MAC, (c)(d) Proposed scheme. CR
and DL in the ﬁgure represent the communication radius and the data packet length,
respectively. Maximum Postponement Numbers are all 1.

大送信見送り回数が 1 以上であれば，B-MAC と比べて高いデータパケット到達率が得られることが分かる．
これは提案手法が，隠れ端末問題を回避し，更にデー
図 11

端末の格子状配置における平均データパケット到
達率の比較．(a) B-MAC, (b) 提案手法
Fig. 11 Comparison of average data packet delivery
ratios in lattice arrangement. (a) B-MAC,(b) Proposed scheme.

タパケットの受信に失敗した場合でも異なる経路から
データパケットを受信できるためである．一方，隠れ端末問題を回避できない B-MAC においてデータパケット到達率が低下している．これは各端末ごとの平均データパケット到達率の分布を示した図 12 (a)，(b)

行った．なお，シミュレーションの開始時，上記の 1 台
は送信モードであるとし，それ以外の端末は通常モードであるとした．その他のシミュレーションの設定を表 2 に示す．∗ 印の付いている項目は本章のシミュ
レーションにおいて常に一定に設定されるものである．

5. 2 端末の格子状配置におけるデータパケット到
達率の比較
以上のような環境下で B-MAC 及び提案手法の平均
データパケット到達率の比較を行い結果を図 11 に示す．図は，横軸を通信可能半径とし，縦軸を平均データ

及び (c)，(d) の比較からも明らかである（図 12 の最大送信見送り回数は全て 1 である）．隠れ端末問題を回避できる提案手法（図 12 (c)，(d)）では，全ノードブロードキャスト開始端末からのホップ数の増加に伴いデータパケット到達率が単調に低下している．一方，隠れ端末問題を回避できない B-MAC（図 12 (a)，(b)）では，全ノードブロードキャスト開始端末からのホップ数にかかわらずデータパケット到達率が局所的に低下しており，通信可能半径に依存したデータパケット到達率の空間パターンが生じている（注 11）．

パケット到達率としたものである．平均データパケッ
ト到達率は，最大送信見送り回数（Max. Post.）が 0，

1，2 のそれぞれに対して示してある．図 11 (a) と (b)の通信可能半径 1 の場合に注目すると，提案手法は最144（注 11）：図 12 ではデータパケット到達率の空間パターンを明瞭に示す
ため，カラーバーの下限値をデータパケット到達率の最低値よりも大きくとっている．それぞれのデータパケット到達率の最低値は以下のとおりである：(a) 89.68%，(b) 99.02%，(c) 99.19%，(d) 99.5%．

論文／受信端末始動通信による非同期型フラッディングプロトコルの提案とシミュレーション評価

しかし，図 11 (a) と (b) の通信可能半径 3 以上の場合に注目すると，B-MAC において提案手法を上回る平均データパケット到達率が得られていることが分かる．これは B-MAC においてプリアンブル同士が衝突している場合でもデータパケットの送受信が成功していることを示している．送信端末始動の B-MAC
では，データパケット送信端末が各々のタイミングで
データパケットを送信しているために，プリアンブル
同士が衝突している場合であっても，必ず最後までプ
リアンブル及びデータパケットを送信する端末が存在する．この場合，100slot ほどの比較的送信時間の短いデータパケットならばデータパケットの受信に成功する場合が多発する．一方，提案手法では最大送信見
送り回数を 1 以上に設定することで，通信可能半径が3 以上の場合でも B-MAC と遜色のないデータパケッ
ト到達率が得られる．
以上から条件によっては B-MAC が高いデータパケット到達率を得られるが，提案手法は最大送信見送
り回数を 1 以上に設定することで，さまざまな環境において，ある一定以上のデータパケット到達率を期待できることが明らかになった．

5. 3 端末の格子状配置における各種性能の比較
本節では，両手法の平均データパケット到達率が同水準になる条件の下で，全ノードブロードキャストに要する時間や全端末の消費電力量を比較する．更に，これらの性能比較を踏まえ，提案手法がどのような応用に向いているのかを明らかにする．
シミュレーション設定は，B-MAC の最大送信見送

図 13

端末の格子状配置における各種性能を表すヒスト
グラムの比較．(a) データパケット到達率，(b) 全
ノードブロードキャストに要する時間，(c) 全端末の消費電力量Fig. 13 Comparison of histograms showing various performances in lattice arrangement.
(a) Data packet delivery ratio, (b) End-toend delay, (c) Total power consumption.

り回数を 1，提案手法の最大送信見送り回数を 2 とする以外は表 2 に従うものとした（このとき，両手法の平均データパケット到達率が同水準になることは以下に要する時間の平均値（ave.）に注目すると，提案手で示される）．

法は B-MAC よりも全ノードブロードキャストに要す

図 13 に両手法の (a) データパケット到達率，(b) 全

る時間が 2 倍以上かかることが分かる．この遅延の主ノードブロードキャストに要する時間，(c) 全端末の消な要因は，提案手法がハンドシェイクの手順を含むの

費電力量のヒストグラムを示す．はじめに，図 13 (a)に対し，B-MAC がそれを含まないことによる．最後のデータパケット到達率について両手法を比較する．

に，図 13 (c) の全端末の消費電力量について両手法を

図 13 (a) の右の拡大図（Enlarged view）に注目する比較する．図 13 (c) の全端末の消費電力量の平均値と，両手法のデータパケット到達率の差は 0.01%であ（ave.）に注目すると，提案手法は B-MAC の消費電

り，本節の設定において，両手法のデータパケット到

力量の 20%ほどに抑えられていることが分かる．この達率は同水準であることが認められる．これにより高い省電力性の主な要因は，受信端末始動である提案

全ノードブロードキャストに要する時間と消費電力量

手法が，送信端末始動である B-MAC のような Longのフェアな比較が可能になる．次に，図 13 (b) の全

Preamble を使わないため，消費電力の大きなパケッ

ノードブロードキャストに要する時間について両手法

ト送信に費やす時間を大幅に小さくできていることにを比較する．図 13 (b) の全ノードブロードキャスト

よる．
145

電子情報通信学会論文誌 2019/3 Vol. J102–A No. 3

以上より，提案手法は，全ノードブロードキャスト

補助金（課題番号 26286086），並びに電気通信普及財に要する時間よりも，省電力に高いデータパケット到団研究調査助成を受けて行われた．本研究の初期段階

達率を得ることを優先するような応用に向いているこでの菊地正隆君（現・日立コンサルティング），東峯とが分かった．

圭佑君（現・日産オートモーティブテクノロジー）の6. む す び
本研究は，分散ネットワークにおける新規な全ノー協力に深謝します．
文[1]“Internet of Things (IoT): A vision, architectural el-

ドブロードキャスト手法を提案し，系統的なシミュレー

ements, and future directions,” Future Generation

ションにより提案手法の特性（特に，データパケット

Computer Systems, vol.29, no.7, pp.1645–1660, Sept.

到達率）を明らかにした．更に，全ノードブロードキャ
ストを行う際の現実的な環境の下で，従来の送信端末
始動の手法よりも省電力に高いデータパケット到達率が得られる可能性を示した．

2013. DOI:10.1016/j.future.2013.01.010[2]小牧省三，間瀬憲一，松江英明，守倉正博，無線 LAN とユビキタスネットワーク，丸善，東京，2004.

[3]

クロスボー株式会社，XM2110J/MPR2600J/420/520MIB Users Manual, http://www.xbow.jp/mprmib.
pdf, July 2008.

[4]

H.-A. Tanaka, Y. Ouyang, Y. Yabe, I. Nishikawa, and

本研究では 1 端末からの全ノードブロードキャストを想定したが，（提案手法 [9] に含まれるという意味

K. Nakada, “Better clock synchronization from si-

で）本研究と同等のプロトコルにより 2 種類のデータ

multaneous two skew estimations,” Nonlinear Theory

パケットを 2 端末から全ノードブロードキャストする

and Its Applications (NOLTA), vol.7, no.4, pp.548–

ことも想定可能であり，その場合でも提案手法は省電力性を低下させることなく高いデータパケット到達率

献

J. Gubbi, R. Buyya, S. Marusic, and M. Palaniswami,

556, Oct. 2016. DOI:10.1587/nolta.7.548[5]

Y. Sun, O. Gurewitz, and D.B. Johnson, “RI-を維持可能である [32], [33]．すなわち，提案手法は 1.

MAC: A receiver-initiated asynchronous duty cy-

で述べた必要最小限の構成にもかかわらず，さまざま

wireless sensor networks,” Proc. 6th ACM Int.

な設定環境において，省電力性と高いデータパケット

Conf. on Embedded Networked Sensor Systems

到達率の両立が可能と考えられる．

(SenSys ’08), pp.1–14, Raleigh, USA, Nov. 2008.

従来手法の B-MAC と本研究の提案する RI-MAC

cle MAC protocol for dynamic traﬃc loads in

DOI:10.1145/1460412.1460414
[6]

R.C.

Carrano,ベースの手法は，動作機構の差異のみならず，制御パ

andC.V.N.

ケットの種類や送信頻度の差や任意性が大きいため，

omy

of

全ノードブロードキャストに要する時間や消費電力量

sensor

networks,”

torials,

vol.16,のフェアな比較は容易ではない．これらの性能は想定する環境や回路により大きく左右されるからである．

cyclingmechanisms

IEEE

no.1,

Commun.

pp.181–194,

Magalhães,
andtaxon-

inwireless

Surv.

Tu-

June

2014.

X. Fafoutis, A.D. Mauro, M.D. Vithanage, andtrol protocols for wireless sensor networks,” Computer

全ノードブロードキャストに要する時間と全端末の消Networks,

vol.76,

pp.55–74,

Jan.

2015.

DOI:10.1016/j.comnet.2014.11.002[8]

菊地正隆，田中久陽，“省電力センサネットワークにおけ” 信学
るコリジョン回避型ブロードキャスト手法の提案，
技報，AN2008-3, May 2008.

[9]

田中久陽，菊地正隆，木村崇之，“情報処理装置および方” 特許第 5177416 号，法，プログラム，並びに通信方法，
出願日 2008 年 11 月 7 日，https://jstore.jst.go.jp/

ト手法の各種性能を比較するフェアな方法の確立が必本研究の提案する手法は考え得る最も簡素な通信機
能（デバイス）のみを必要とする点で有効であると考

nationalPatentDetail.html?pat id=26364&

えられる．起動受信機（wake-up receiver）のように付加的な回路を導入した高度な応用（例えば [34]）は

duty

L.C.S.
“SurveyN. Dragoni, “Receiver-initiated medium access con-ト到達率について，それが同水準となる設定の下で，要であると考えられる．

Passos,

DOI:10.1109/SURV.2013.052213.00116[7]

本研究では，フェアな比較が容易であるデータパケッ

費電力量を比較した．今後，全ノードブロードキャス

D.

Albuquerque,

ssn=UC211P21S010 2，登録日 2013 年 1 月 18 日．
[10]

W.

Ye,

J.

Heidemann,

and

D.

Estrin,“An

目指さず，データパケット到達率のみを重視し即時応

energy-eﬃcient MAC protocol for wireless sen-答性を必要としない応用に有効と考えられる．

sor

謝辞 日頃ご議論いただく複雑コミュニケーション
サイエンス研究会並びに非線形問題研究会の諸氏に感謝します．本研究の一部は平成 27 年度文科省科研費
146

networks,”

Proc.

IEEE

INFOCOM

2002,

vol.3, pp.1567–1576, New York, USA, June 2002.
DOI:10.1109/INFCOM.2002.1019408[11]

J. Polastre, J. Hill, and D. Culler, “Versatile low
power media access for wireless sensor networks,”論文／受信端末始動通信による非同期型フラッディングプロトコルの提案とシミュレーション評価
July 2013. DOI:10.1109/EUROCON.2013.6624999

Proc. 2nd Int. Conf. on Embedded Network Sensor
Systems (SenSys ’04), pp.95–107, Baltimore, USA,[22]

畠内孝明，福山良和，石井美里，四蔵達之，“メッシュネッ
トワークのためのポーリングによる低消費電力型アクセス方式の提案，” 電学論 C，vol.128, no.12, pp.1761–1766,
Dec. 2008. DOI:10.1541/ieejeiss.128.1761[23]

D. Kominami, M. Sugano, M. Murata, and T.

Nov. 2004. DOI:10.1145/1031495.1031508[12]

M. Sekine, S. Nakamura, and K. Sezaki, “Anenergy-eﬃcient protocol for active/sleep schedulesynchronization in wireless sensor networks,” Proc.
12th Asia-Paciﬁc Conf. on Commun. (APCC ’06),

Hatauchi, “Energy-eﬃcient receiver-driven wirelesspp.816–820, Busan, South Korea, Aug.-Sept. 2006.

mesh sensor networks,” Sensors, vol.11, no.1, pp.111–

DOI:10.1109/APCC.2006.255873[13]137, Jan. 2011. DOI: 10.3390/s110100111

M. Buettner, G.V. Yee, E. Anderson, and R. Han,

[24]

“X-MAC: A short preamble MAC protocol for duty-

slot synchronisation for broadcast messaging for low-

cycled wireless sensor networks,” Proc. 4th Int.

power wireless embedded systems,” Proc. 5th Int.

Conf. on Embedded Networked Sensor Systems (Sen-

Conf. on Communication System Software and Mid-

Sys ’06), pp.307–320, Boulder, USA, Oct.-Nov. 2006.

dleware (COMSWARE ’11), no.9, Verona, Italy, July

DOI:10.1145/1182807.1182838[14]2011. DOI:10.1145/2016551.2016560

K.-J. Wong and D.K. Arvind, “SpeckMAC: Low-

[25]

An asynchronous receiver-initiated ultra low powertransmissions in specknets,” Proc. 2nd Int. Workshop

MAC protocol for wireless sensor networks,” Proc.

on Multi-Hop Ad Hoc Networks: From Theory to

IET Int. Conf. on Wireless Sensor Network (IET-

Reality (REALMAN ’06), pp.71–78, Florence, Italy,

WSN 2010), pp.393–398, Beijing, China, Nov. 2010.

C.J.

Merlinadaptation

and
of

W.B.

Heinzelman,

low-power-listening

wireless sensor networks,”
Comput.,[16]

vol.9,

no.5,

DOI:10.1049/cp.2010.1085“Schedule

protocols

[26]

for

Johnson, “ADB: An eﬃcient multihop broadcast
protocol based on asynchronous duty-cycling in

pp.672–685,

May

2010.

wireless sensor networks,” Proc. 7th ACM Int.

DOI:10.1109/TMC.2009.153

Conf. on Embedded Networked Sensor Systems

E.-Y.A. Lin, J.M. Rabaey, and A. Wolisz, “Power-(SenSys ’09), pp.43–56, Berkeley, USA, Nov. 2009.

sor networks,” Proc. IEEE ICC, vol.7, no.WN05-1,

DOI:10.1145/1644038.1644044[27]

cient receiver-initiated single-hop broadcast protocol

DOI:10.1109/ICC.2004.1313259

for asynchronous MAC in wireless sensor networks,”

E.-Y.A. Lin, J.M. Rabaey, S. Wiethoelter, andRecent Advances in Computer Science and Informa-

A. Wolisz, “Receiver initiated rendezvous schemestion Engineering (Lecture Notes in Electrical Engi-

for sensor networks,” Proc. IEEE GLOBECOM ’05,

neering, vol.127), eds. Z. Qian, L. Cao, W. Su, T.

vol.5, no.WC22.5, pp.3117–3122, St. Louis, USA,Wang, and H. Yang, pp.261–266, Springer, Berlin,

1578331[19]

2012. DOI:10.1007/978-3-642-25769-8 38[28]

uniﬁed unicast and broadcast traﬃc in multi-hop

ing mobile robots to harvest data from sensor ﬁelds,”

wireless sensor networks,” Proc. 7th IEEE Int. Conf.

IEEE Wireless Commun., vol.16, no.1, pp.22–28,

on Distributed Computing in Sensor Systems andFeb. 2009. DOI:10.1109/MWC.2009.4804365

Workshops (DCOSS), pp.1–9, Barcelona, Spain, June

B. Greßmann, H. Klimek, and V. Turau, “Support-

2011. DOI:10.1109/DCOSS.2011.5982142[29]

N. Pletcher, S. Gambini, and J. Rabaey, “A 2GHz

Proc. 8th Int. Workshop on Intelligent Transporta-

52µW wake-up receiver with −72dBm sensitivity us-

tion (WIT 2011), Hamburg, Germany, March 2011.

ing uncertain-IF architecture,” Proc. IEEE Interna-

M. Sugano, “Combining sender- and receiver-driven

tional Solid-State Circuits Conference, pp.525–526

MAC protocols for a large-scale metering system
based on potential routing,” 2013 10th Int. Conf.

[21]

P. Yadav and J.A. McCann, “YA-MAC: Handling

O. Tekdas, V. Isler, J.H. Lim, and A. Terzis, “Us-ing intelligent passenger ﬂows in airport terminals,”[20]

Y. Qiu, S. Li, D. Yang, and Z. Li, “RWB: An eﬃ-

pp.3769–3776, Paris, France, June 2004.

Nov.-Dec. 2005. DOI:10.1109/GLOCOM.2005.
[18]

Y. Sun, O. Gurewitz, S. Du, L. Tang, and D.B.

IEEE Trans. Mobile

eﬃcient rendez-vous schemes for dense wireless sen-

[17]

D. Yang, Y. Qiu, S. Li, and Z. Li, “RW-MAC:

power decentralised MAC protocols for low data rate

May 2006. DOI:10.1145/1132983.1132996[15]

P. Yadav and J.A. McCann, “EBS: Decentralised

and 633, Feb. 2008.
[30]

X. Huang, S. Rampu, X. Wang, G. Dolmans, andand Expo on Emerging Technologies for a Smarter

H. De Groot, “A 2.4GHz/915MHz 51µW wake-up

World (CEWIT), pp.1–6, Melville, USA, Oct. 2013.

receiver with oﬀset and noise suppression,” Proc.

DOI:10.1109/CEWIT.2013.6713748

IEEE International Solid-State Circuits Conference,

M.D. Vithanage, X. Fafoutis, C.B. Andersen, and N.
Dragoni, “Medium access control for thermal energy

pp.222–223, Feb. 2010.
[31]

http://synchro4.ee.uec.ac.jp/download/[32]

東峯圭佑，ユビキタスコンピューティング環境におけるフharvesting in advanced metering infrastructures,”IEEE EuroCon 2013, pp.291–299, Zagreb, Croatia,

IEICE2018a/

147電子情報通信学会論文誌 2019/3 Vol. J102–A No. 3[33]

ラッディングを想定した省電力衝突回避型ブロードキャス

田中 久陽

ト手法の構築と性能評価，平成 23 年度修士論文，電気通信大学情報システム基盤学専攻，2012.
東峯圭佑，田中久陽，“無線センサネットワークにおける” 電子情
省電力ブロードキャスト手法の構築と性能評価，

1990 早大電気卒．1992 同大学大学院理工学研究科修士課程修了．1995 同大学院
理工学研究科博士後期課程修了．博士 (工報通信学会第 3 回複雑コミュニケーションサイエンス研究
会 (CCS)，2012. http://synchro4.ee.uec.ac.jp/
literature/higashimine CCS3 2012.pdf[34]

H. Yomo, T. Kawamoto, K. Abe, Y. Ezure, T. Ito,
A. Hasegawa, and T. Ikenaga, “ROD-SAN: Energyeﬃcient and high-response wireless sensor and actuator networks employing wake-up receiver,” IEICE
Trans. Commun., vol.E99-B, no.9, pp.1998–2008,
Sept. 2016. DOI:10.1587/transcom.2016SNP0013（平成 30 年 6 月 27 日受付，9 月 17 日再受付）

中川

正基

（正員）

2005 早大理工物理卒．2007 同大学大学
院理工学研究科修士課程修了．2012 同大

学院先進理工学研究科博士後期課程単位取得退学．2012〜2015 同大学先進理工学部
応用物理学科助手．2015 年 3 月博士（理学）．同年より，広島大学大学院理学研究科数理分子生命理学専攻研究員．2016 同大クロマチン動態数
理研究拠点特任助教．2017 電通大大学院情報理工学研究科研究員，現在に至る．注入同期現象や自律分散通信ネットワークなどの工学的応用研究，触媒反応ネットワークやクロマチン動態などの生命科学数理モデル解析，非線形力学（特にカオス・
エルゴード理論）の研究に従事．

慶田朗

1996 成蹊大学工学部経営工学科卒．1998
電気通信大学大学院情報システム学研究科

修士課程修了．同年より，セイコーインス
ツル株式会社入社．2007 東京大学医科学研究所研究支援員．2012 NEC システム
テクノロジー株式会社，オリンパスソフト
ウェアテクノロジー株式会社，株式会社 NTT ドコモ，日本電
気航空宇宙システム株式会社，(株) 東京システム技研などへのソフトウェア設計開発派遣業務を経て，2017 電気通信大学大学院情報理工学研究科非常勤職員．

148（正員：シニア会員）

学)．同年より，日本学術振興会特別研究員(PD)．1996 カリフォルニア大バークレー校客員研究員．1997 ソニーコンピューター
サイエンス研究所研究員．2001 電通大大学院電気通信学研究科助教授 (現在，情報理工学研究科・准教授)，現在に至る．情報通信システム，非線形物理等の分野横断的領域の研究に従事．
2006，2007，2009 第 22 回電気通信普及財団賞 (テレコムシ
ステム技術賞)，第 23 回，第 25 回電気通信普及財団賞 (テレコムシステム奨励賞) 各受賞．2015 電子情報通信学会平成 27

年度 NOLTA ソサイエティ功労賞受賞．著書に「非線形ダイ
ナミクスとカオス 数学的基礎から物理・生物・化学・工学への応用まで」（中尾裕也，千葉逸人と共訳 2015）等がある．