(57)【要約】【課題】  モバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法を提供することを課題とする。【解決手段】  本発明は、モバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法として提案され、モバイルエッジのシナリオ下で、全体的なオフロードスキームを採用することによってもたらすインタラクション能力を喪失し、基地局の帯域幅ストレスが増える問題を解決する。具体的実現ステップは、次の通りであり、すなわちオフロードコンピューティングが必要なタスクを相互依存関係のある異なるサブタスクに分割し、各サブタスクは個別にコンピューティング処理を行うことができ、同時にグラフ内のオフロード不可能なサブタスクノード位置を決定する。次に、各サブタスク間の依存関係に応じて、重み付き有向非巡回グラフを生成し、グラフ内の各ノードはデータの計算量を表し、各エッジが異なるコンポーネント間のデータ通信量を表す。次に蟻コロニーアルゴリズムを使用して各オフロード可能なサブタスクの具体的実行位置を繰り返し算出し、すなわちエッジコンピューティングサーバーにオフロードするか、ローカルで演算を完了するかを確認する。最後にモバイルデバイスエネルギー消費の削減を目的とし、蟻コロニーアルゴリズムに基づくシングルタスクオフロード戦略の準最適解が得られる。【選択図】図１
2021525402.tif 000002
【特許請求の範囲】
【請求項１】
モバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法であって、次のステップを含み、
ステップ１：ランダムタスクが到着すると、キャッシュキューに一時的に格納され、システムが前記タスクの実行をケジューリングすると、タスクを個別に実行でき複数のサブタスクに分割し、集合V={v1,v2,…vi,…vj,…,vN}として表わすことができ、Ｎはサブタスクの総数を示し、同時にＶを２組の異なる集合Vloc,Voff⊆Ｖ、に分割し、ここで、Vlocがローカルで実行しなければならないオフロード不可能なコンポーネントを示し、Voffが意思決定に用いられ、ＭＥＣサーバーにオフロードできるコンポーネント集合を示し；また各タスクセットＶには、一意の入り口トランザクションおよび出口トランザクションがあり、前記入り口トランザクションには先行トランザクションがなく、出口トランザクションに後続トランザクションがなく；各タスク間の依存関係を表すため、バイナリ変数Eij∈{0,1}も定義し、下式（１）で表され、
【数１】
2021525402.tif 000012
のeijが存在し、最後にサブタスクセットＶとトランザクション依存関係セットＥを通じて有向非巡回グラフG=(V,E)を形成し；
ステップ２：タスクコンピューティングとタスク伝送のエネルギー消費モデルを組み合わせてタスクの総エネルギー消費モデルを確立し、総エネルギー消費モデルの各パラメータを初期化し；
ステップ３：各経路内のフェロモン濃度、タスクサイクル数ｔおよび各サイクル中の蟻の数ｍを初期化し； 
ステップ４：蟻コロニーアルゴリズムを利用して各蟻が選択された経路を得て、ステップ２で設計されたタスクの総エネルギー消費モデルに従って、すべてのｍ個の蟻が選択された経路から最小エネルギー消費Emin(A)に対応する経路を今回のタスクサイクル下の好ましいタスクオフロード戦略として選択し、今回のタスクサイクル下のすべてのｍ個の蟻がタスクを完了してから、ステップ５に進み；
ここで、蟻が選択する経路は、オフロードコンピューティング確率で決まり、ｔ回目のタスクサイクル下で各蟻のサブタスクｉオフロードコンピューティングの確率Pic(t)の計算式は、下式（４）の通りであり；
【数４】
2021525402.tif 000013
上式中の各記号の意味は、次の通りであり；
ｔ：タスクサイクル数を表し；
τic(t)：ｔ時刻にタスクｉをＭＥＣサーバーにオフロードする経路上のフェロモン濃度を表し；
τil(t)：ｔ時刻にタスクｉをローカルで計算する経路上のフェロモン濃度を表し；
α：フェロモンヒューリスティックファクターを表し、フェロモンの蟻の経路選択に対するフェロモンの影響を反映し；
2021525402.tif 000014
β：ヒューリスティック関数ファクターを表し、これは蟻コロニー検索の誘導におけるヒューリスティック関数の相対的な重要性を反映し；
ステップ５：あらかじめ設定されたタスクサイクル数に達していない場合、フェロモン濃度を更新させ、ステップ４に戻ってより適切なタスクオフロード戦略を探し続け；あらかじめ設定されたタスクサイクル数に達した場合、ステップ６に進み；
前記フェロモン濃度の更新公式は、次の通りであり、  
【数５】
2021525402.tif 000015
ここで、ρは、フェロモンの蒸発係数であり、1-ρが残ったフェロモン係数を表し、Δτic(t,t+1)が１ラウンドのタスク反復後のフェロモンの増分を表し、下式（６）によって計算され、
【数６】
2021525402.tif 000016
ｍは、１サイクル内の蟻の総数であり、Δτick(t,t+1)がｋ番目の蟻によりタスクｉのタスクオフロード経路上に排出されたフェロモンを表し、各蟻によりタスクｉのオフロード経路上に排出されたフェロモンを下式（７）で表し、ここでＱが正規数であり、各蟻が排出したフェロモン量を制御するために用いられ；
【数７】
2021525402.tif 000017
ここで、Emin(A)は、t回目のタスクサイクルに対応する最小エネルギー消費を表し；
ステップ６：最終回のタスクサイクルで得られた好ましいタスクオフロード戦略は、最適なタスクオフロード戦略であり、最適なタスクオフロード戦略に基づきタスクを割り当て、エッジコンピューティングを実行する、
ことを特徴とする、モバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法。
【請求項２】
前記ステップ３に記載のフェロモン濃度は、蟻コロニーアルゴリズムの実行開始時のオフロード経路における各サブタスクのフェロモン濃度τc(0)={τ1c(0),……,τNc(0)}および非オフロード経路におけるサブタスクのフェロモン濃度τl(0)={τ1l(0),……,τNl(0)}を含み、かつ∀vi∈Voffに対して、τic(0)=τil(0)=δ、δ∈(0,1)が存在し、∀vi∈Vlocに対して、τil(0)=+∞が存在することを特徴とする、請求項１に記載のモバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法。
【請求項３】
前記ステップ２に記載のタスクコンピューティングエネルギー消費モデルは、次の通りであり、すなわちタスクがローカルで実行される場合、ローカルでタスクを実行するモバイルデバイスのエネルギー消費がEl=PlTlであり、PlはローカルＣＰＵがタスクを実行する時の電力量であり、タスク実行時間Tl=ωifl-1で、ωiがタスクの計算量を表し、flがローカルデバイスのＣＰＵ実行速度を表し；
タスクがＭＥＣサーバー側で実行される場合、モバイルデバイスの基本的なエネルギー消費はEb=PbTcであり、ここで、PbがモバイルデバイスのＣＰＵアイドル時の電力を表し、タスク実行時間が Tc=ωifc-1で、fcがＭＥＣサーバーのＣＰＵ実行速度を表し；
ステップ２に記載のタスク伝送のエネルギー消費モデルは、次の通りであり、
タスクｊがＭＥＣサーバー側で実行され、かつその先行タスクｉがモバイルデバイス側で実行される場合、消耗される能量はEijs=PsTijsであり、タスクの伝送時間がTijs=eijRs-1であり；
タスクｊがモバイル側で実行され、その先行タスクがＭＥＣサーバー側で実行される場合、消耗される能量はEijr=PrTijrであり、タスクの伝送時間がTijr=eijRr-1であり；
ここで、RsおよびRrは、データアップロードのチャネル速度およびデータダウンロードのチャネル速度をそれぞれ表し、PsおよびPrがデータ送信とデータ受信時の通信電力をそれぞれ表し；
ステップ２に記載のタスクの総エネルギー消費モデルは、次の通りであり、
【数３】
2021525402.tif 000018
【数２】
2021525402.tif 000019
ことを特徴とする、請求項１に記載のモバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、モバイルエッジコンピューティング分野に関し、特に、モバイルデバイスタスクオフロードのエネルギー消費削減を目的として、設計された蟻コロニーアルゴリズムに基づくシングルタスクオフロード戦略に関する。
【背景技術】
【０００２】
スマートフォン或いはタブレットＰＣ等のモバイル端末の普及は、モバイルネットワークおよびワイヤレスネットワークへの影響が非常に深刻であり、これにより世界のモバイルネットワークに革命を起こした。このようなモバイルデバイスは、低ストレージ容量、高電力消費、低帯域幅および高レイテンシのネットワーク環境に直面している。モバイルクラウドコンピューティング（ＭＣＣ）は、クラウドコンピューティングとモバイルコンピューティングの統合として、モバイルデバイスにかなりの能力をもたらし、集中型クラウドを通じてストレージ、コンピューティングおよびエネルギーを提供する。しかしながら、大量のモバイルデバイスが登場するにつれ、ＭＣＣが高レイテンシ、セキュリティの脆弱性および狭いネットワークカバレッジなど、より深刻な課題に直面している。次世代のモバイルネットワーク（５Ｇなど）のシナリオにおいて、これらの問題がより顕著になる可能性がある。シスコビジュアルネットワーキングインデックスが発表した最近のレポートによると、２０２０年になると、１１６億台のモバイル接続デバイスが世界中で使用されるようになる。日増しに増大するネットワーク需要を解決するため、モバイルエッジコンピューティング（ＭＥＣ）の概念が生まれた。ＭＥＣの主な目的は、ＭＣＣシステムの課題を解決することである。ＭＥＣは、クラウドリソース（例えばストレージおよびコンピューティング能力）を無線アクセスネットワークのエッジにデプロイすることによってＭＣＣの能力を増強する。これはエンドユーザーに高速で強力なコンピューティング能力、エネルギー効率、ストレージ容量、移動性および環境感知のサポートを提供する。以前は、ｃｌｏｕｄｌｅｔと呼ばれるインターネットエッジ技術がモバイルクラウドサービスをデプロイするために導入されていた。ただし、限られたＷｉＦｉカバレッジ範囲によりｃｌｏｕｄｌｅｔは、従来の課題を解決することができなかった。したがって、ＭＥＣの研究分野には未だ解決すべき課題が山積されている。
【０００３】
アカデミックな世界では、Ｒｕｄｅｎｋｏ  Ａ氏らが最も早くからタスクオフロードによりモバイルデバイスのエネルギー消費を効果的に削減して動作時間を延長できることを提案した。この研究は、ノートパソコンから計算量が複雑なプログラムをリモートデスクトップコンピュータにアップロードする実験により、上述の推測を検証した。Ｗｅｎ  ＹおよびＺｈａｎｇ  Ｗ氏らは、共同で最適化されたタスクオフロードスキームを提案し、モバイルアプリがモバイルデバイス上にローカルで実行される場合、モバイルデバイスのクロック周波数を最適にスケジューリングすることにより、コンピューティングのエネルギー消費が最小化され、モバイルアプリがクローンされたクラウドで実行される場合、無線チャネルの伝送電力の構成によって伝送のエネルギー消費を最小化する。タスクオフロードアルゴリズムを実行すると、モバイルデバイスのコンピューティングリソースおよびエネルギーが消費されるため、Ｈｕｅｒｔａ−Ｃａｎｅｐａ  Ｇ氏らは、モバイルアプリの実行履歴と現在のアプリケーションステータスに基づいてタスクオフロードを行うスキームを提案した。このスキームは、タスクオフロード決定の適応調整を設定し：モバイルデバイ自体に十分なコンピューティングリソースとバッテリー電力がある場合、動的決定スキームを使用してタスク実行パフォーマンスを改善し；モバイルデバイス自体にリソースが不足している場合、履歴状態に基づいて、タスク実行前にオフロードを決定することで、動的な決定による追加オーバーヘッドを減らする。タスクオフロードの時に、ワイヤレスネットワークもタスク完了のエネルギー消費にも影響を及ぼし、Ｈｕａｎｇ  ＤおよびＷａｎｇ  Ｐ氏らは、ワイヤレスネットワーク環境に応じてタスクオフロード戦略を動的に変更する方法を提案し、モバイルアプリを複数のサブタスクの有向非巡回グラフとして構築し、各サブタスクの実行位置を割り当てることにより、モバイルアプリ実行のエネルギー消費を最小化させる。
【０００４】
さらに、一部の研究では、タスクの実行時間とエネルギー消費を同時に最適化されている。Ｗｕ  Ｈｕａｍｉｎｇ氏らは、実行時間の短縮とエネルギー消費の節約のバランスをとるタスクオフロードスキームを提案し、クラウドコンピューティングリソースの弾力性およびオンデマンドの割り当てを実現した。Ｌｉ  Ｔｉａｎｚｅ氏らは、ＭＥＣ環境でのタスクオフロードに用いられるエネルギー消費、時間遅延およびサーバーの実行コストを統合する最適化スキームを提案した。複数のターゲットが共存するタスクオフロードアルゴリズムの複雑さは高すぎることがよくあり、オフロードアルゴリズムの時間の複雑さを軽減するため、Ｗａｎｇ  Ｊ氏らがリアプノフ（Ｌｙａｐｕｎｏｖ）最適化理論に基づく複雑さの低いタスクオフロードアルゴリズムを提案し、かつ同時に実行時間およびモバイルデバイスのエネルギー消費を削減できる。
【０００５】
従来のモバイルクラウドコンピューティング環境に対比して、新しいモバイルエッジコンピューティング環境において、ユーザーとＭＥＣサーバーの距離をさらに近づけることで、タスクオフロードのデータ伝送における通信オーバーヘッドを大幅に削減させる。従来のタスクオフロード戦略を策定する時、タスクを一体として見され、オフロードされた場合、すべてのタスクをＭＥＣサーバーに渡して処理され、オフロードされない場合、タスクがローカルで実行される。このようなオフロード戦略は、サーバーと頻繁にデータ通信を行うモバイルデバイスにとって明らかに最適ではない。本発明によって提案されるシングルタスクを分割すると共にオフロード決定を策定するタスクオフロード方法は、タスク実行パフォーマンスを向上し、タスク実行オーバーヘッドを削減し、コンピューティングタスク粒度を細かく分割する。この時タスクの具体的な特性（タスクトポロジ構造、タスク計算量、タスク間で伝送されるデータ量のサイズなど）を利用してタスクオフロードアルゴリズムを設計することも特に重要である。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
従来の技術的手段において、タスクオフロード決定を実行する際、１つのタスクを単位としてオフロード決定される。モバイルデバイスとの頻繁なインタラクションを必要とする現実のシナリオには多くのタスクがあり、これらの操作はローカルで実行する必要がある。これにより、従来の技術的手段には、現実のシナリオに適さない部分がある。モバイルエッジのシナリオにおいて、ユーザーのモバイルデバイスは、通信事業者の基地局と頻繁にインタラクトし、全体的にオフロードスキームを採用すると、インタラクション能力を喪失すると共に基地局の帯域幅ストレスが増えることで、これは明らかに実際のアプリに適していない。
【０００７】
本発明は、シングルユーザーＭＥＣシステムにおける蟻コロニーアルゴリズムタスクに基づくオフロード戦略を設計し、アプリを複数のサブタスクを含む有向グラフに変換することにより、蟻コロニーアルゴリズム内のフェロモンの概念を導入して現在のサブタスクオフロード決定の確率を計算し、モバイルデバイスのエネルギー消費の最小化を最適化の目標として一組のスケジューリング戦略を生成し、アルゴリズムを何度も繰り返して演算し、生成されたスケジューリング戦略を継続的に最適化することで、最適なタスクスケジューリング戦略に近づけていく。本発明は、各サブタスクの状況を十分に考慮し、全体的なオフロード戦略を策定し、各オフロード不可能なサブタスクをローカルで実行することで、ユーザーのインタラクションのニーズを満たすことができ、現実のシナリオにより適しており、最適化効率を向上させる。
【０００８】
本発明では、上記目的を達成するために、次の技術的手段を講じ、前記技術的手段は次のステップを含む。すなわち、
ステップ１として、ランダムタスクが到着すると、キャッシュキューに一時的に格納され、システムが前記タスクの実行をケジューリングすると、タスクを個別に実行でき複数のサブタスクに分割し、集合V={v1,v2,…vi,…vj,…,vN}として表わすことができ、Ｎはサブタスクの総数を示す。同時にＶを２組の異なる集合Vloc、Voff⊆Ｖに分割し、ここで、Vlocがローカルで実行しなければならないオフロード不可能なコンポーネントを示し、Voffが意思決定に用いられ、ＭＥＣサーバーにオフロードできるコンポーネント集合を示す。また各タスクセットＶには、一意の入り口トランザクションおよび出口トランザクションがあり、前記入り口トランザクションには先行トランザクションがなく、出口トランザクションに後続トランザクションがない。本発明は、各タスク間の依存関係を表すため、バイナリ変数Eij∈{0,1}も定義し、下式（１）で表される。
【０００９】
【数１】
2021525402.tif 000003
【００１０】
∀Eij=1に対して、いずれもタスクｉとタスクｊの間のデータ伝送量を表すための１個のeijが存在する。最後にサブタスクセットＶとトランザクション依存関係セットＥを通じて有向非巡回グラG=(V,E)を形成する。
【００１１】
ステップ２として、モバイルエッジコンピューティングモデルの各項目パラメータを決定して初期化し、エネルギー消費モデルを確立する。
【００１２】
本発明によって提案されるタスクオフロード戦略の目的は、モバイルデバイス側の実行のエネルギー消費を最適化することであり、このためタスク実行の位置（ローカル実行又はＭＥＣ側実行）を定義する必要があり、集合A=｛A1,A2,……,AN｝で各タスクの実行位置を示し、かつ∀Ai∈{0,1}は下式（２）で表される。
【００１３】
【数２】
2021525402.tif 000004
【００１４】
本発明ではω（ＣＰＵ ｃｙｃｌｅｓ）を用いてタスク計算量を示し、fがデバイスのＣＰＵ実行速度を示し、Ｔがタスクの実行時間を示す。タスクがローカルで実行される場合、ローカル実行時間をTl=wifl-1とすることができる。コンピューティング速度がfcのＭＥＣサーバー側でタスクを実行する時、タスクの完了に必要な時間はTc=wifc-1である。
【００１５】
Pは、ＣＰＵがタスクを実行する時の電力量単位（Ｗ）であると仮定すると、モバイルデバイスがローカルでタスクを実行するためのＣＰＵのエネルギー消費がEl=PlTlで表すことができる。ＭＥＣサーバー側でタスクを実行する場合、モバイル側はタスク演算を実行する必要がないものとするが、デバイスの動作を維持するために基本的なエネルギーを消費する必要があり、エネルギー消費をEb=PbTcで表される。ここで、Pb(W)は、モバイルデバイスのＣＰＵアイドル時の電力を表し、Tc(s)がモバイルデバイスのアイドル時間を表す。PbがPlよりはるかに小さいため、タスクオフロード戦略はモバイルデバイスのエネルギー消費を節約できる。
【００１６】
データ伝送の消費において、RsおよびRrを用いてデータアップロードのチャネル速度（モバイル側からＭＥＣ側へ）およびデータダウンロードのチャネル速度（ＭＥＣ側からモバイル側へ）をそれぞれ表し、単位が（ｂｉｔ／ｓ）であり、PsおよびPrがデータ送信とデータ受信時の通信電力をそれぞれ表し、単位が(W)である。
【００１７】
タスクｊがＭＥＣサーバー側で実行され、かつその先行タスクｉがモバイル側で実行される場合、タスクの伝送時間はTijs =eijRs-1である。消費されるエネルギーがEijs=PsTijsである。
【００１８】
タスクｊがモバイル側で実行され、その先行タスクがＭＥＣサーバー側で実行される場合、タスクの伝送時間はTijr=eijRr-1である。消費されるエネルギーはEijr=PsTijrである。上記構築されたエネルギー消費モデルによると、単一のアプリ実行を完了するためのモバイルデバイス全体の総エネルギー消費は、下式（３）で表されることができる。
【００１９】
【数３】
2021525402.tif 000005
【００２０】
Ｎは、サブタスクの総数を表し、等式の右側の第二部分が１番目のサブタスクより最後
2021525402.tif 000006
いずれもモバイルデバイス又はＭＥＣサーバーで演算する場合、伝送のエネルギー消費を発生しない。最後のサブタスクは、ローカルで実行されることが決定され、かつ後続タスクがないため、そのタスクのエネルギー消費をエネルギー消費計算モデルの一番先頭に加える。
【００２１】
これまで、タスクをモバイルデバイスの総エネルギー消費E(A)を最小化するモデルとして確立し、各オフロード可能なタスクにはオ、フロード又は非オフロードという２つの選択肢があるため、Ｎ個のタスクの総オフロード決定に2N個の解がある。列挙法でタスクの最適なエネルギー消費の解を算出した場合、時間の複雑さが高すぎ、実際の生産に適していない。したがって、本発明でこと蟻コロニーアルゴリズムでこの複雑なタスクモデルを解決する。
【００２２】
ステップ３として、各経路内のフェロモン濃度、タスクサイクル数ｔおよび蟻の数ｍを初期化する。
【００２３】
タスク実行の具体的なエネルギー消費を算出するため、各サブタスクの実際の計算位置、すなわち集合A=｛A1,A2,……,AN｝の値を決定しなければならない。各サブタスクに必要なタスク計算量およびデータ通信量が異なり、タスクのエネルギー消費を可能な限り削減するため我々は、コンピューティング依存型のサブタスクをエッジコンピューティングノードに伝送して演算し、データ通信量が高いが、計算量の少ないサブタスクをモバイルデバイスに引き渡してローカルで処理させる傾向がある。蟻コロニーアルゴリズムは、異なる経路上のフェロモン濃度に従ってタスクオフロード確率を算出し、したがってタスクオフロード戦略が得られる。本発明が使用するτc(0)={τ1c(0)、……、τNc(0)}、τl(0)={τ1l(0)、……、τNl(0)}は、それぞれ蟻コロニーアルゴリズムの実行開始時、オフロード経路および非オフロード経路における各サブタスクのフェロモン濃度を表し、∀vi∈Voffに対して、τic(0)=τil(0)=δ、(δ∈(0,1))が存在する。∀vi∈Vlocに対して、τil(0)=+∞が存在する。同時に、タスクサイクル数および各サイクル中の蟻の数ｍを初期化する。
【００２４】
ステップ４として、蟻コロニーアルゴリズムを利用して各蟻が選択された経路を得て、ステップ２で設計されたタスクの総エネルギー消費モデルに従って、すべてのｍ個の蟻が選択された経路から最小エネルギー消費Emin(A)に対応する経路を今回のタスクサイクル下の好ましいタスクオフロード戦略として選択し、今回のタスクサイクル下のすべてのｍ個の蟻がタスクを完了してから、ステップ５に進む。
【００２５】
ここで、蟻が選択する経路は、オフロードコンピューティング確率で決まり、ｔ回目のタスクサイクル下で各蟻のサブタスクｉオフロードコンピューティングの確率Pic(t)の計算式は、下式（４）の通りである。
【００２６】
【数４】
2021525402.tif 000007
上式中の各記号の意味は、次の通りである。
ｔ：タスクサイクル数および時刻を表し；
τic(t)：ｔ時刻にタスクｉをＭＥＣサーバーにオフロードする経路上のフェロモン濃度を表し；
τil(t)：ｔ時刻にタスクｉをローカルで計算する経路上のフェロモン濃度を表し；
α：フェロモンヒューリスティックファクター(α∈[0,5])を表し、フェロモンの蟻の経路選択に対するフェロモンの影響を反映し；
2021525402.tif 000008
β：ヒューリスティック関数ファクター(β∈[0,5])を表し、これは蟻コロニー検索の誘導におけるヒューリスティック関数の相対的な重要性を反映する。
【００２７】
式（４）から各サブタスクの実行位置を得た後、蟻の数ｋをリセットし、各蟻はこのラウンドのタスクオフロード戦略に従ってタスクを実行し、ステップ２で設計されたエネルギー消費モデルに基づき、各蟻が選択した経路のエネルギー消費を算出すると共に最小エネルギー消費Emin(A)を更新する。このラウンドの全てのｍ個の蟻は、タスクを完了してから、ステップ５に進む。
【００２８】
ステップ５として、あらかじめ設定されたタスクサイクル数に達していない場合、フェロモン濃度を更新させ、ステップ４に戻ってより適切なタスクオフロード戦略を探し続け；あらかじめ設定されたタスクサイクル数に達した場合、ステップ６に進む。
【００２９】
前記フェロモン濃度の更新公式は、次の通りである。
【００３０】
【数５】
2021525402.tif 000009
ここで、ρは、フェロモンの蒸発係数(ρ∈[0.1,0.99])であり、1-ρが残ったフェロモン係数を表し、Δτic(t,t+1)が１ラウンドのタスク反復後のフェロモンの増分を表し、下式（６）によって計算される。
【００３１】
【数６】
2021525402.tif 000010
【００３２】
ｍは、１サイクル内の蟻の総数であり、Δτick(t,t+1)がｋ番目の蟻によりタスクｉのタスクオフロード経路上に排出されたフェロモンを表し、各蟻によりタスクｉのオフロード経路上に排出されたフェロモンを下式（７）で表し、ここでＱが正規数(Q∈[1,10])であり、各蟻が排出したフェロモン量を制御するために用いられる。
【００３３】
【数７】
2021525402.tif 000011
【００３４】
ステップ６として、最終回のタスクサイクルで得られた好ましいタスクオフロード戦略は、最適なタスクオフロード戦略であり、最適なタスクオフロード戦略に基づきタスクを割り当て、エッジコンピューティングを実行する。
【発明の効果】
【００３５】
従来技術と比べると、本発明は、以下の利点を有する。
本発明の設計は、実際のＭＥＣシナリオにおいて、モバイルユーザーとの頻繁なインタラクションを必要とする多くのアプリがあることを視野に入れ、これらアプリ全体のオフロード演算が間違いなく通信オーバーヘッドを増加させることにより、モバイルデバイスのエネルギー消費が高くなる。本発明は、処理待ちのアプリを先に複数のサブタスクを含む有向グラフに変換し、次に蟻コロニーアルゴリズムを利用して処理待ちのタスクグラフを複数回トラバースすることで、最後にエネルギー消費を最適化目標とするタスクオフロード戦略の準最適解が得られる。その他のアルゴリズムと比較して、タスク実行の効率確保を踏まえ、タスク実行の時間の複雑さを軽減させ、同時にタスク粒度を細かく分割する方法により、モバイルデバイスのエネルギー消費を最大限に削減し、ＭＥＣシステム全体のサービス品質が向上される。
【００３６】
以下、本発明の目的、技術的手段をより分かりやすくため、図面を参照しつつ本発明をさらに説明する。
【図面の簡単な説明】
【００３７】
【図１】本発明の細粒度タスク分割図である。
【図２】タスク実行の流れ図である。
【発明を実施するための形態】
【００３８】
ステップ１として、図１は、アプリの細粒度タスク分割図である。本発明は、アプリを独立して実行する複数のサブタスクに分割し、有向グラフG=(V,E)で表される。図１内のノードv∈Vは、分割されたサブタスクを表し、図１内のエッジeij∈Eがタスクの間の伝送データを表し、例えば：eijはタスクiの実行完了後、eijのデータをタスクjに伝送し、タスクjがタスクi実行完了後で伝送してきたデータを受信した後でのみ実行を開始できることを表す。図内のサブタスクは、２つのカテゴリに分けることができ、１つはローカルで実行しなければならないタスク（例えばユーザーのオーディオおよびビデオコレクションとモバイル端末のインタラクション等）で、図１内の中実タスク１、４、６として表され、｛１，４，６｝⊆Ｖｌｏｃと表示され；もう１つは、図１内の中空タスク２、３、５のようなオフロード可能なタスクであり、｛２，３，５｝⊆Ｖｏｆｆと表示される。
【００３９】
本発明は、各タスク間の依存関係を表すため、バイナリ変数Eij∈{0,1}も定義し、下式（１）で表される。Eij=1の場合、タスクｉの実行完了後にのみタスクｊは実行を開始でき、それ以外の場合、Eij=0である。例えば図１では、E12=1,E45=1,E63=0、、であり、タスクに２つ以上の先行タスクがある場合、すべての先行タスクが完了した後で実行できる。
【００４０】
ステップ２として、モバイルエッジコンピューティングのエネルギー消費モデルを確立し、タスクパラメータを初期化する。本発明は、エネルギー消費モデルをローカルコンピューティングのエネルギー消費およびオフロードコンピューティングのエネルギー消費という２つの部分に分ける。各サブタスクの計算量をそれぞれwi（ＣＰＵ  ｃｙｃｌｅｓ）、ＣＰＵ実行速度をfl、コンピューティング実行時の電力をPlとすると、タスクローカル実行のエネルギー消費はEl=Plwifl-1と表すことができる。タスクにオフロードコンピューティングを必要とする場合、モバイルデバイスがタスクオフロード期間の待機時エネルギー消費は、Eb=Pbwifc-1で表すことができ、同時にタスクオフロードでは必ず通信エネルギー消費が発生するため、本発明はそれぞれEijs=PseijRs-1およびEijr=PseijRr-1でデータのアップロードおよびダウンロードのエネルギー消費を表す。本発明によって提案されるタスクオフロード戦略の目的は、モバイルデバイス側の実行のエネルギー消費を最適化することであり、このためタスク実行の位置（ローカル実行又はＭＥＣ側実行）を定義する必要があり、Ai∈｛0,1｝であるタスクの実行位置を表す。明らかに、ローカルで実行しなければならないタスクは、モバイルデバイスでのみ演算できるため、∀vi∈Vloc,Ai=1である。タスクの総エネルギー消費は、式（３）で表されることができる。
【００４１】
ステップ３として、ステップ２を踏まえ、タスク実行の具体的なエネルギー消費を得たい場合、集合A=｛A1,A2,……,AN｝の値を決定するだけでよい。まず初期化されたフェロモン濃度τc(0),τl(0)、および式（４）に従って、初ラウンドのタスクオフロード確率Pic(0)を算出する。次に、１ラウンド目のｋ個の蟻は、Pic(0)を通じてそれぞれ初のタスクオフロード戦略A=｛A1,A2,……,AN｝の値を求めることができ、（求解法：P1c(0)=λと仮定すると、この時完全ランダム化法を通じて数字μ∈(0,1)を生成し、0＜λ≦μの場合、A1=1となり、1＞λ＞μの場合、A1=0となる。）最後に式（３）でタスクの総エネルギー消費を得ることができ、このｋ個のエネルギー消費から最小値を選択して、Emin(A)と記録された。
【００４２】
ステップ４として、最小エネルギー消費Emin(A)および式（５）〜（７）に従って、異なる経路のフェロモン濃度を更新する。新しいフェロモン濃度および式（４）で次ラウンドのタスク割り当て確率Pic(t)を算出し、Pic(t)を通じて新しいタスクオフロード戦略Ａを得ることで、続いて最適なエネルギー消費Emin(A)を更新できる。
【００４３】
ステップ５として、あらかじめ設定されたタスクサイクル数ｔに達していない場合、ステップ４に戻ってより適切なタスクオフロード戦略を探し続け；あらかじめ設定されたタスクサイクル数ｔに達した場合、ステップ６に進む。
【００４４】
ステップ６として、最終回のタスクサイクルで得られた好ましいタスクオフロード戦略は、最適なタスクオフロード戦略であり、最適なタスクオフロード戦略に基づきタスクを割り当て、エッジコンピューティングを実行する。具体的実行の流れ図は、図２に示す通りである。
【図１】
2021525402.tif 000020
【図２】
2021525402.tif 000021
【手続補正書】
【提出日】令和2年8月21日(2020.8.21)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】  本発明は、モバイルエッジコンピューティング分野に関し、特に、モバイル端末タスクオフロードのエネルギー消費削減を目的として、設計された蟻コロニーアルゴリズムに基づくシングルタスクオフロード戦略に関する。
【背景技術】
【０００２】  スマートフォン或いはタブレットＰＣ等のモバイル端末の普及は、モバイルネットワークおよびワイヤレスネットワークへの影響が非常に深刻であり、これにより世界のモバイルネットワークに革命を起こした。このようなモバイル端末は、低ストレージ容量、高電力消費、低帯域幅および高レイテンシのネットワーク環境に直面している。モバイルクラウドコンピューティング（ＭＣＣ）は、クラウドコンピューティングとモバイルコンピューティングの統合として、モバイル端末にかなりの能力をもたらし、集中型クラウドを通じてストレージ、コンピューティングおよびエネルギーを提供する。しかしながら、大量のモバイル端末が登場するにつれ、ＭＣＣが高レイテンシ、セキュリティの脆弱性および狭いネットワークカバレッジなど、より深刻な課題に直面している。次世代のモバイルネットワーク（５Ｇなど）のシナリオにおいて、これらの問題がより顕著になる可能性がある。シスコビジュアルネットワーキングインデックスが発表した最近のレポートによると、２０２０年になると、１１６億台のモバイル接続デバイスが世界中で使用されるようになる。日増しに増大するネットワーク需要を解決するため、モバイルエッジコンピューティング（ＭＥＣ）の概念が生まれた。ＭＥＣの主な目的は、ＭＣＣシステムの課題を解決することである。ＭＥＣは、クラウドリソース（例えばストレージおよびコンピューティング能力）を無線アクセスネットワークのエッジにデプロイすることによってＭＣＣの能力を増強する。これはエンドユーザーに高速で強力なコンピューティング能力、エネルギー効率、ストレージ容量、移動性および環境感知のサポートを提供する。以前は、ｃｌｏｕｄｌｅｔと呼ばれるインターネットエッジ技術がモバイルクラウドサービスをデプロイするために導入されていた。ただし、限られたＷｉＦｉカバレッジ範囲によりｃｌｏｕｄｌｅｔは、従来の課題を解決することができなかった。したがって、ＭＥＣの研究分野には未だ解決すべき課題が山積されている。【０００３】  アカデミックな世界では、Ｒｕｄｅｎｋｏ  Ａ氏らが最も早くからタスクオフロードによりモバイル端末のエネルギー消費を効果的に削減して動作時間を延長できることを提案した。この研究は、ノートパソコンから計算量が複雑なプログラムをリモートデスクトップコンピュータにアップロードする実験により、上述の推測を検証した。Ｗｅｎ  ＹおよびＺｈａｎｇ  Ｗ氏らは、共同で最適化されたタスクオフロードスキームを提案し、モバイルアプリがモバイル端末上にローカルで実行される場合、モバイル端末のクロック周波数を最適にスケジューリングすることにより、コンピューティングのエネルギー消費が最小化され、モバイルアプリがクローンされたクラウドで実行される場合、無線チャネルの伝送電力の構成によって伝送のエネルギー消費を最小化する。タスクオフロードアルゴリズムを実行すると、モバイル端末のコンピューティングリソースおよびエネルギーが消費されるため、Ｈｕｅｒｔａ−Ｃａｎｅｐａ  Ｇ氏らは、モバイルアプリの実行履歴と現在のアプリケーションステータスに基づいてタスクオフロードを行うスキームを提案した。このスキームは、タスクオフロード決定の適応調整を設定し：モバイル端末自体に十分なコンピューティングリソースとバッテリー電力がある場合、動的決定スキームを使用してタスク実行パフォーマンスを改善し；モバイル端末自体にリソースが不足している場合、履歴状態に基づいて、タスク実行前にオフロードを決定することで、動的な決定による追加オーバーヘッドを減らする。タスクオフロードの時に、ワイヤレスネットワークもタスク完了のエネルギー消費にも影響を及ぼし、Ｈｕａｎｇ  ＤおよびＷａｎｇ  Ｐ氏らは、ワイヤレスネットワーク環境に応じてタスクオフロード戦略を動的に変更する方法を提案し、モバイルアプリを複数のサブタスクの有向非巡回グラフとして構築し、各サブタスクの実行位置を割り当てることにより、モバイルアプリ実行のエネルギー消費を最小化させる。【０００４】  さらに、一部の研究では、タスクの実行時間とエネルギー消費を同時に最適化されている。Ｗｕ  Ｈｕａｍｉｎｇ氏らは、実行時間の短縮とエネルギー消費の節約のバランスをとるタスクオフロードスキームを提案し、クラウドコンピューティングリソースの弾力性およびオンデマンドの割り当てを実現した。Ｌｉ  Ｔｉａｎｚｅ氏らは、ＭＥＣ環境でのタスクオフロードに用いられるエネルギー消費、時間遅延およびサーバーの実行コストを統合する最適化スキームを提案した。複数のターゲットが共存するタスクオフロードアルゴリズムの複雑さは高すぎることがよくあり、オフロードアルゴリズムの時間の複雑さを軽減するため、Ｗａｎｇ  Ｊ氏らがリアプノフ（Ｌｙａｐｕｎｏｖ）最適化理論に基づく複雑さの低いタスクオフロードアルゴリズムを提案し、かつ同時に実行時間およびモバイル端末のエネルギー消費を削減できる。【０００５】  従来のモバイルクラウドコンピューティング環境に対比して、新しいモバイルエッジコンピューティング環境において、ユーザーとＭＥＣサーバーの距離をさらに近づけることで、タスクオフロードのデータ伝送における通信オーバーヘッドを大幅に削減させる。従来のタスクオフロード戦略を策定する時、タスクを一体として見され、オフロードされた場合、すべてのタスクをＭＥＣサーバーに渡して処理され、オフロードされない場合、タスクがローカルで実行される。このようなオフロード戦略は、サーバーと頻繁にデータ通信を行うモバイル端末にとって明らかに最適ではない。本発明によって提案されるシングルタスクを分割すると共にオフロード決定を策定するタスクオフロード方法は、タスク実行パフォーマンスを向上し、タスク実行オーバーヘッドを削減し、コンピューティングタスク粒度を細かく分割する。この時タスクの具体的な特性（タスクトポロジ構造、タスク計算量、タスク間で伝送されるデータ量のサイズなど）を利用してタスクオフロードアルゴリズムを設計することも特に重要である。
【発明の概要】
【発明が解決しようとする課題】
【０００６】  従来の技術的手段において、タスクオフロード決定を実行する際、１つのタスクを単位としてオフロード決定される。モバイル端末との頻繁なインタラクションを必要とする現実のシナリオには多くのタスクがあり、これらの操作はローカルで実行する必要がある。これにより、従来の技術的手段には、現実のシナリオに適さない部分がある。モバイルエッジのシナリオにおいて、ユーザーのモバイル端末は、通信事業者の基地局と頻繁にインタラクトし、全体的にオフロードスキームを採用すると、インタラクション能力を喪失すると共に基地局の帯域幅ストレスが増えることで、これは明らかに実際のアプリに適していない。【０００７】  本発明は、シングルユーザーＭＥＣシステムにおける蟻コロニーアルゴリズムタスクに基づくオフロード戦略を設計し、アプリを複数のサブタスクを含む有向グラフに変換することにより、蟻コロニーアルゴリズム内のフェロモンの概念を導入して現在のサブタスクオフロード決定の確率を計算し、モバイル端末のエネルギー消費の最小化を最適化の目標として一組のスケジューリング戦略を生成し、アルゴリズムを何度も繰り返して演算し、生成されたスケジューリング戦略を継続的に最適化することで、最適なタスクスケジューリング戦略に近づけていく。本発明は、各サブタスクの状況を十分に考慮し、全体的なオフロード戦略を策定し、各オフロード不可能なサブタスクをローカルで実行することで、ユーザーのインタラクションのニーズを満たすことができ、現実のシナリオにより適しており、最適化効率を向上させる。【０００８】  本発明では、上記目的を達成するために、次の技術的手段を講じ、前記技術的手段は次のステップを含む。すなわち、  ステップ１として、ランダムタスクが到着すると、キャッシュキューに一時的に格納され、前記タスクの実行をスケジューリングすると、タスクを個別に実行でき複数のサブタスクに分割し、集合V={v1,v2,…vi,…vj,…,vN}として表わすことができ、Ｎはサブタスクの総数を示す。同時にＶを２組の異なる集合Vloc、Voff⊆Ｖに分割し、ここで、Vlocがローカルで実行しなければならないオフロード不可能なコンポーネントを示し、Voffが意思決定に用いられ、ＭＥＣサーバーにオフロードできるコンポーネント集合を示す。また各タスクセットＶには、一意の入り口トランザクションおよび出口トランザクションがあり、前記入り口トランザクションには先行トランザクションがなく、出口トランザクションに後続トランザクションがない。本発明は、各タスク間の依存関係を表すため、バイナリ変数Eij∈{0,1}も定義し、下式（１）で表される。【０００９】
【数１】
2021525402.tif 000022
【００１０】∀Eij=1に対して、いずれもタスクｉとタスクｊの間のデータ伝送量を表すための１個のeijが存在する。最後にサブタスクセットＶとトランザクション依存関係セットＥを通じて有向非巡回グラG=(V,E)を形成する。【００１１】  ステップ２として、モバイルエッジコンピューティングモデルの各項目パラメータを決定して初期化し、エネルギー消費モデルを確立する。【００１２】  本発明によって提案されるタスクオフロード戦略の目的は、モバイル端末側の実行のエネルギー消費を最適化することであり、このためタスク実行の位置（ローカル実行又はＭＥＣ側実行）を定義する必要があり、集合A=｛A1,A2,……,AN｝で各タスクの実行位置を示し、かつ∀Ai∈{0,1}は下式（２）で表される。【００１３】
【数２】
2021525402.tif 000023
【００１４】  本発明ではω（ＣＰＵ ｃｙｃｌｅｓ）を用いてタスク計算量を示し、fがデバイスのＣＰＵ実行速度を示し、Ｔがタスクの実行時間を示す。タスクがローカルで実行される場合、ローカル実行時間をTl=wifl-1とすることができる。コンピューティング速度がfcのＭＥＣサーバー側でタスクを実行する時、タスクの完了に必要な時間はTc=wifc-1である。【００１５】  Pは、ＣＰＵがタスクを実行する時の電力量単位（Ｗ）であると仮定すると、モバイル端末がローカルでタスクを実行するためのＣＰＵのエネルギー消費がEl=PlTlで表すことができる。ＭＥＣサーバー側でタスクを実行する場合、モバイル側はタスク演算を実行する必要がないものとするが、デバイスの動作を維持するために基本的なエネルギーを消費する必要があり、エネルギー消費をEb=PbTcで表される。ここで、Pb(W)は、モバイル端末のＣＰＵアイドル時の電力を表し、Tc(s)がモバイル端末のアイドル時間を表す。PbがPlよりはるかに小さいため、タスクオフロード戦略はモバイル端末のエネルギー消費を節約できる。【００１６】  データ伝送の消費において、RsおよびRrを用いてデータアップロードのチャネル速度（モバイル側からＭＥＣ側へ）およびデータダウンロードのチャネル速度（ＭＥＣ側からモバイル側へ）をそれぞれ表し、単位が（ｂｉｔ／ｓ）であり、PsおよびPrがデータ送信とデータ受信時の通信電力をそれぞれ表し、単位が(W)である。【００１７】  タスクｊがＭＥＣサーバー側で実行され、かつその先行タスクｉがモバイル側で実行される場合、タスクの伝送時間はTijs =eijRs-1である。消費されるエネルギーがEijs=PsTijsである。【００１８】  タスクｊがモバイル側で実行され、その先行タスクがＭＥＣサーバー側で実行される場合、タスクの伝送時間はTijr=eijRr-1である。消費されるエネルギーはEijr=PsTijrである。上記構築されたエネルギー消費モデルによると、単一のアプリ実行を完了するためのモバイル端末全体の総エネルギー消費は、下式（３）で表されることができる。【００１９】
【数３】
2021525402.tif 000024
【００２０】  Ｎは、サブタスクの総数を表し、等式の右側の第二部分が１番目のサブタスクより最後2021525402.tif 000025
いずれもモバイル端末又はＭＥＣサーバーで演算する場合、伝送のエネルギー消費を発生しない。最後のサブタスクは、ローカルで実行されることが決定され、かつ後続タスクがないため、そのタスクのエネルギー消費をエネルギー消費計算モデルの一番先頭に加える。【００２１】  これまで、タスクをモバイル端末の総エネルギー消費E(A)を最小化するモデルとして確立し、各オフロード可能なタスクにはオ、フロード又は非オフロードという２つの選択肢があるため、Ｎ個のタスクの総オフロード決定に2N個の解がある。列挙法でタスクの最適なエネルギー消費の解を算出した場合、時間の複雑さが高すぎ、実際の生産に適していない。したがって、本発明でこと蟻コロニーアルゴリズムでこの複雑なタスクモデルを解決する。【００２２】  ステップ３として、各経路内のフェロモン濃度、タスクサイクル数ｔおよび蟻の数ｍを初期化する。【００２３】  タスク実行の具体的なエネルギー消費を算出するため、各サブタスクの実際の計算位置、すなわち集合A=｛A1,A2,……,AN｝の値を決定しなければならない。各サブタスクに必要なタスク計算量およびデータ通信量が異なり、タスクのエネルギー消費を可能な限り削減するため我々は、コンピューティング依存型のサブタスクをエッジコンピューティングノードに伝送して演算し、データ通信量が高いが、計算量の少ないサブタスクをモバイル端末に引き渡してローカルで処理させる傾向がある。蟻コロニーアルゴリズムは、異なる経路上のフェロモン濃度に従ってタスクオフロード確率を算出し、したがってタスクオフロード戦略が得られる。本発明が使用するτc(0)={τ1c(0)、……、τNc(0)}、τl(0)={τ1l(0)、……、τNl(0)}は、それぞれ蟻コロニーアルゴリズムの実行開始時、オフロード経路および非オフロード経路における各サブタスクのフェロモン濃度を表し、∀vi∈Voffに対して、τic(0)=τil(0)=δ、(δ∈(0,1))が存在する。∀vi∈Vlocに対して、τil(0)=+∞が存在する。同時に、タスクサイクル数および各サイクル中の蟻の数ｍを初期化する。【００２４】  ステップ４として、蟻コロニーアルゴリズムを利用して各蟻が選択された経路を得て、ステップ２で設計されたタスクの総エネルギー消費モデルに従って、すべてのｍ個の蟻が選択された経路から最小エネルギー消費Emin(A)に対応する経路を今回のタスクサイクル下の好ましいタスクオフロード戦略として選択し、今回のタスクサイクル下のすべてのｍ個の蟻がタスクを完了してから、ステップ５に進む。【００２５】  ここで、蟻が選択する経路は、オフロードコンピューティング確率で決まり、ｔ回目のタスクサイクル下で各蟻のサブタスクｉオフロードコンピューティングの確率Pic(t)の計算式は、下式（４）の通りである。【００２６】
【数４】
2021525402.tif 000026
上式中の各記号の意味は、次の通りである。  ｔ：タスクサイクル数および時刻を表し；  τic(t)：ｔ時刻にタスクｉをＭＥＣサーバーにオフロードする経路上のフェロモン濃度を表し；  τil(t)：ｔ時刻にタスクｉをローカルで計算する経路上のフェロモン濃度を表し；  α：フェロモンヒューリスティックファクター(α∈[0,5])を表し、フェロモンの蟻の経路選択に対するフェロモンの影響を反映し；2021525402.tif 000027
β：ヒューリスティック関数ファクター(β∈[0,5])を表し、これは蟻コロニー検索の誘導におけるヒューリスティック関数の相対的な重要性を反映する。
【００２７】  式（４）から各サブタスクの実行位置を得た後、蟻の数ｋをリセットし、各蟻はこのラウンドのタスクオフロード戦略に従ってタスクを実行し、ステップ２で設計されたエネルギー消費モデルに基づき、各蟻が選択した経路のエネルギー消費を算出すると共に最小エネルギー消費Emin(A)を更新する。このラウンドの全てのｍ個の蟻は、タスクを完了してから、ステップ５に進む。【００２８】  ステップ５として、あらかじめ設定されたタスクサイクル数に達していない場合、フェロモン濃度を更新させ、ステップ４に戻ってより適切なタスクオフロード戦略を探し続け；あらかじめ設定されたタスクサイクル数に達した場合、ステップ６に進む。【００２９】  前記フェロモン濃度の更新公式は、次の通りである。【００３０】
【数５】
2021525402.tif 000028
ここで、ρは、フェロモンの蒸発係数(ρ∈[0.1,0.99])であり、1-ρが残ったフェロモン係数を表し、Δτic(t,t+1)が１ラウンドのタスク反復後のフェロモンの増分を表し、下式（６）によって計算される。
【００３１】
【数６】
2021525402.tif 000029
【００３２】  ｍは、１サイクル内の蟻の総数であり、Δτick(t,t+1)がｋ番目の蟻によりタスクｉのタスクオフロード経路上に排出されたフェロモンを表し、各蟻によりタスクｉのオフロード経路上に排出されたフェロモンを下式（７）で表し、ここでＱが正規数(Q∈[1,10])であり、各蟻が排出したフェロモン量を制御するために用いられる。【００３３】
【数７】
2021525402.tif 000030
【００３４】  ステップ６として、最終回のタスクサイクルで得られた好ましいタスクオフロード戦略は、最適なタスクオフロード戦略であり、最適なタスクオフロード戦略に基づきタスクを割り当て、エッジコンピューティングを実行する。
【発明の効果】
【００３５】  従来技術と比べると、本発明は、以下の利点を有する。  本発明の設計は、実際のＭＥＣシナリオにおいて、モバイルユーザーとの頻繁なインタラクションを必要とする多くのアプリがあることを視野に入れ、これらアプリ全体のオフロード演算が間違いなく通信オーバーヘッドを増加させることにより、モバイル端末のエネルギー消費が高くなる。本発明は、処理待ちのアプリを先に複数のサブタスクを含む有向グラフに変換し、次に蟻コロニーアルゴリズムを利用して処理待ちのタスクグラフを複数回トラバースすることで、最後にエネルギー消費を最適化目標とするタスクオフロード戦略の準最適解が得られる。その他のアルゴリズムと比較して、タスク実行の効率確保を踏まえ、タスク実行の時間の複雑さを軽減させ、同時にタスク粒度を細かく分割する方法により、モバイル端末のエネルギー消費を最大限に削減し、ＭＥＣシステム全体のサービス品質が向上される。【００３６】  以下、本発明の目的、技術的手段をより分かりやすくため、図面を参照しつつ本発明をさらに説明する。
【図面の簡単な説明】
【００３７】
【図１】本発明の細粒度タスク分割図である。
【図２】タスク実行の流れ図である。
【発明を実施するための形態】
【００３８】  本発明は、基地局とモバイル端末を含むモバイルネットワーク環境において、基地局にＭＥＣサーバーを設置したシステムを用いる。ＭＥＣサーバーはマルチアクセスエッジコンピューティング（Multi-access Edge Computing）技術として知られており、モバイル端末からの要求に対して、ブロードキャスト情報を送信し、該情報に基づいてモバイル端末が現在の環境でのエネルギー消費の最適化を目的としたタスクオフロード戦略を策定するものである。
【００３９】  モバイル端末はスマートフォン或いはタブレットＰＣ等で構成され、周知のように演算手段であるＣＰＵやそれと協働するメモリ等、モニタ、入力手段、通信回線を介して基地局と通信する通信手段を有する。ＭＥＣサーバーも周知のサーバー装置の基本的な構成を備えており、演算手段であるＣＰＵやそれと協働するメモリ等の他、通信回線を介して基地局と通信する通信手段を有する。
【００４０】  本発明はこのようなシステム構成において次の処理をコンピュータにより実行するものである。  ステップ１として、図１は、アプリの細粒度タスク分割図である。本発明は、モバイル端末の演算手段が、アプリを独立して実行する複数のサブタスクに分割する。概念としては有向グラフG=(V,E)で表される。図１内のノードv∈Vは、分割されたサブタスクを表し、図１内のエッジeij∈Eがタスクの間の伝送データを表し、例えば：eij（図中ではすべてaijと表示している。以下同じ）はタスクiの実行完了後、eijのデータをタスクjに伝送し、タスクjがタスクi実行完了後で伝送してきたデータを受信した後でのみ実行を開始できることを表す。図内のサブタスクは、２つのカテゴリに分けることができ、１つはローカルで実行しなければならないタスク（例えばユーザーのオーディオおよびビデオコレクションとモバイル端末のインタラクション等）で、図１内の中実タスク１、４、６として表され、｛１，４，６｝⊆Ｖｌｏｃと表示され；もう１つは、図１内の中空タスク２、３、５のようなオフロード可能なタスクであり、｛２，３，５｝⊆Ｖｏｆｆと表示される。すなわち中実タスク１、４、６はモバイル端末の演算手段を用いて実行され、中空タスク２、３、５はＭＥＣサーバーの演算手段によって実行するように分けることができる。
【００４１】  本発明は、各タスク間の依存関係を表すため、バイナリ変数Eij∈{0,1}も定義し、前述した（１）で表される。Eij=1の場合、タスクｉの実行完了後にのみタスクｊは実行を開始でき、それ以外の場合、Eij=0である。例えば図１では、E12=1,E45=1,E63=0、であり、タスクに２つ以上の先行タスクがある場合、すべての先行タスクが完了した後で実行できる。
【００４２】  ステップ２として、モバイル端末の演算手段が、モバイルエッジコンピューティングのエネルギー消費モデルを確立し、タスクパラメータを初期化する。本発明は、エネルギー消費モデルをローカルコンピューティング（モバイル端末側）のエネルギー消費およびオフロードコンピューティング（ＭＥＣサーバー側）のエネルギー消費という２つの部分に分ける。各サブタスクの計算量をそれぞれwi（ＣＰＵ  ｃｙｃｌｅｓ）、ＣＰＵ実行速度をfl、コンピューティング実行時の電力をPlとすると、タスクローカル実行のエネルギー消費はEl=Plwifl-1と表すことができる。タスクにオフロードコンピューティングを必要とする場合、モバイル端末がタスクオフロード期間の待機時エネルギー消費は、Eb=Pbwifc-1で表すことができ、同時にタスクオフロードでは必ず通信エネルギー消費が発生するため、本発明はそれぞれEijs=PseijRs-1およびEijr=PseijRr-1でデータのアップロードおよびダウンロードのエネルギー消費を表す。本発明によって提案されるタスクオフロード戦略の目的は、モバイル端末側の実行のエネルギー消費を最適化することであり、このためタスク実行の位置（モバイル端末実行又はＭＥＣ側実行）を定義する必要があり、Ai∈｛0,1｝であるタスクの実行位置を表す。明らかに、ローカルで実行しなければならないタスクは、モバイル端末でのみ演算できるため、∀vi∈Vloc,Ai=1である。タスクの総エネルギー消費は、上述の式（３）で表されることができる。
【００４３】  ステップ３として、ステップ２を踏まえ、モバイル端末の演算手段が、タスク実行の具体的なエネルギー消費を得たい場合、集合A=｛A1,A2,……,AN｝の値を決定するだけでよい。まず蟻コロニーアルゴリズムにおける初期化されたフェロモン濃度τc(0),τl(0)、および式（４）に従って、初ラウンドのタスクオフロード確率Pic(0)を算出する。次に、１ラウンド目のｋ個の蟻は、Pic(0)を通じてそれぞれ初のタスクオフロード戦略A=｛A1,A2,……,AN｝の値を求めることができ、（求解法：P1c(0)=λと仮定すると、この時完全ランダム化法を通じて数字μ∈(0,1)を生成し、0＜λ≦μの場合、A1=1となり、1＞λ＞μの場合、A1=0となる。）最後に式（３）でタスクの総エネルギー消費を得ることができ、このｋ個のエネルギー消費から最小値を選択して、Emin(A)と記録された。
【００４４】  ステップ４として、モバイル端末の演算手段が、最小エネルギー消費Emin(A)および式（５）〜（７）に従って、異なる経路のフェロモン濃度を更新する。新しいフェロモン濃度および式（４）で次ラウンドのタスク割り当て確率Pic(t)を算出し、Pic(t)を通じて新しいタスクオフロード戦略Ａを得ることで、続いて最適なエネルギー消費Emin(A)を更新できる。
【００４５】  ステップ５として、、モバイル端末の演算手段が、あらかじめ設定されたタスクサイクル数ｔに達していない場合、ステップ４に戻ってより適切なタスクオフロード戦略を探し続け；あらかじめ設定されたタスクサイクル数ｔに達した場合、ステップ６に進む。
【００４６】  ステップ６として、、モバイル端末の演算手段が、最終回のタスクサイクルで得られた好ましいタスクオフロード戦略は、最適なタスクオフロード戦略であり、最適なタスクオフロード戦略に基づきタスクを割り当て、モバイル端末の演算手段及び、ＭＥＣサーバーの演算手段がそれぞれエッジコンピューティングを実行する。具体的実行の流れ図は、図２に示す通りである。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
モバイル端末と、ＭＥＣサーバーを有する基地局との間のモバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法であって、次のステップを含み、  ステップ１：モバイル端末において、ランダムタスクが到着すると、キャッシュキューに一時的に格納され、前記タスクの実行をスケジューリングすると、タスクを個別に実行でき複数のサブタスクに分割し、集合V={v1,v2,…vi,…vj,…,vN}として表わすことができ、Ｎはサブタスクの総数を示し、同時にＶを２組の異なる集合Vloc,Voff⊆Ｖ、に分割し、ここで、Vlocがローカルで実行しなければならないオフロード不可能なコンポーネントを示し、Voffが意思決定に用いられ、ＭＥＣサーバーにオフロードできるコンポーネント集合を示し；また各タスクセットＶには、一意の入り口トランザクションおよび出口トランザクションがあり、前記入り口トランザクションには先行トランザクションがなく、出口トランザクションに後続トランザクションがなく；各タスク間の依存関係を表すため、バイナリ変数Eij∈{0,1}も定義し、下式（１）で表され、【数１】
2021525402.tif 000031
のeijが存在し、最後にサブタスクセットＶとトランザクション依存関係セットＥを通じて有向非巡回グラフG=(V,E)を形成し；  ステップ２：モバイル端末において、タスクコンピューティングとタスク伝送のエネルギー消費モデルを組み合わせてタスクの総エネルギー消費モデルを確立し、総エネルギー消費モデルの各パラメータを初期化し；  ステップ３：モバイル端末において、各経路内のフェロモン濃度、タスクサイクル数ｔおよび各サイクル中の蟻の数ｍを初期化し；   ステップ４：モバイル端末において、蟻コロニーアルゴリズムを利用して各蟻が選択された経路を得て、ステップ２で設計されたタスクの総エネルギー消費モデルに従って、すべてのｍ個の蟻が選択された経路から最小エネルギー消費Emin(A)に対応する経路を今回のタスクサイクル下の好ましいタスクオフロード戦略として選択し、今回のタスクサイクル下のすべてのｍ個の蟻がタスクを完了してから、ステップ５に進み；  ここで、蟻が選択する経路は、オフロードコンピューティング確率で決まり、ｔ回目のタスクサイクル下で各蟻のサブタスクｉオフロードコンピューティングの確率Pic(t)の計算式は、下式（４）の通りであり；
【数４】
2021525402.tif 000032
上式中の各記号の意味は、次の通りであり；  ｔ：タスクサイクル数を表し；  τic(t)：ｔ時刻にタスクｉをＭＥＣサーバーにオフロードする経路上のフェロモン濃度を表し；  τil(t)：ｔ時刻にタスクｉをローカルで計算する経路上のフェロモン濃度を表し；  α：フェロモンヒューリスティックファクターを表し、フェロモンの蟻の経路選択に対するフェロモンの影響を反映し；2021525402.tif 000033
β：ヒューリスティック関数ファクターを表し、これは蟻コロニー検索の誘導におけるヒューリスティック関数の相対的な重要性を反映し；  ステップ５：あらかじめ設定されたタスクサイクル数に達していない場合、フェロモン濃度を更新させ、ステップ４に戻ってより適切なタスクオフロード戦略を探し続け；あらかじめ設定されたタスクサイクル数に達した場合、ステップ６に進み；  前記フェロモン濃度の更新公式は、次の通りであり、  
【数５】
2021525402.tif 000034
ここで、ρは、フェロモンの蒸発係数であり、1-ρが残ったフェロモン係数を表し、Δτic(t,t+1)が１ラウンドのタスク反復後のフェロモンの増分を表し、下式（６）によって計算され、
【数６】
2021525402.tif 000035
ｍは、１サイクル内の蟻の総数であり、Δτick(t,t+1)がｋ番目の蟻によりタスクｉのタスクオフロード経路上に排出されたフェロモンを表し、各蟻によりタスクｉのオフロード経路上に排出されたフェロモンを下式（７）で表し、ここでＱが正規数であり、各蟻が排出したフェロモン量を制御するために用いられ；
【数７】
2021525402.tif 000036
ここで、Emin(A)は、t回目のタスクサイクルに対応する最小エネルギー消費を表し；  ステップ６：最終回のタスクサイクルで得られた好ましいタスクオフロード戦略は、最適なタスクオフロード戦略であり、モバイル端末が、最適なタスクオフロード戦略に基づきタスクを割り当て、モバイル端末及びＭＥＣサーバーがそれぞれエッジコンピューティングを実行する、ことを特徴とする、モバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法。
【請求項２】
前記ステップ３に記載のフェロモン濃度は、蟻コロニーアルゴリズムの実行開始時のオフロード経路における各サブタスクのフェロモン濃度τc(0)={τ1c(0),……,τNc(0)}および非オフロード経路におけるサブタスクのフェロモン濃度τl(0)={τ1l(0),……,τNl(0)}を含み、かつ∀vi∈Voffに対して、τic(0)=τil(0)=δ、δ∈(0,1)が存在し、∀vi∈Vlocに対して、τil(0)=+∞が存在することを特徴とする、請求項１に記載のモバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法。
【請求項３】
前記ステップ２に記載のタスクコンピューティングエネルギー消費モデルは、次の通りであり、すなわちタスクがローカルで実行される場合、ローカルでタスクを実行するモバイル端末のエネルギー消費がEl=PlTlであり、PlはローカルＣＰＵがタスクを実行する時の電力量であり、タスク実行時間Tl=ωifl-1で、ωiがタスクの計算量を表し、flがローカルデバイスのＣＰＵ実行速度を表し；  タスクがＭＥＣサーバー側で実行される場合、モバイル端末の基本的なエネルギー消費はEb=PbTcであり、ここで、Pbがモバイル端末のＣＰＵアイドル時の電力を表し、タスク実行時間が Tc=ωifc-1で、fcがＭＥＣサーバーのＣＰＵ実行速度を表し；  ステップ２に記載のタスク伝送のエネルギー消費モデルは、次の通りであり、  タスクｊがＭＥＣサーバー側で実行され、かつその先行タスクｉがモバイル端末側で実行される場合、消耗される能量はEijs=PsTijsであり、タスクの伝送時間がTijs=eijRs-1であり；  タスクｊがモバイル側で実行され、その先行タスクがＭＥＣサーバー側で実行される場合、消耗される能量はEijr=PrTijrであり、タスクの伝送時間がTijr=eijRr-1であり；  ここで、RsおよびRrは、データアップロードのチャネル速度およびデータダウンロードのチャネル速度をそれぞれ表し、PsおよびPrがデータ送信とデータ受信時の通信電力をそれぞれ表し；  ステップ２に記載のタスクの総エネルギー消費モデルは、次の通りであり、【数３】
2021525402.tif 000037
【数２】
2021525402.tif 000038
ことを特徴とする、請求項１に記載のモバイルエッジコンピューティングのシナリオでシングルタスクオフロード戦略を策定する方法。
【国際調査報告】
2021525402.tif 000039
2021525402.tif 000040
2021525402.tif 000041
2021525402.tif 000042
2021525402.tif 000043