京都大学教育研究振興財団助成事業
成 果 報 告 書
平成20年9月20日
財団法人京都大学教育研究振興財団
会 長

辻

井

昭

雄

様

所属部局・研究科 情報学研究科
職 名・学 年

助 教

氏

新 熊 亮 一名

事 業 区 分平成２０年度 ・ 長期派遣助成

研 究 課 題 名

コグニティブ無線を用いた周波数資源制御技術の研究

受 入 機 関アメリカ合衆国ラトガース（Rutgers）大学WINLAB

渡 航 期 間

平成２０年８月２６日

成 果 の 概 要

タイトルは「成果の概要／報告者名」として、A４版２０００字程度・和文で作成し、添付して下さい。 「成果の概要」以外に添付する資料 □ 無■有( 発表論文2件 )〜平成２１年９月４日

交付 を受 けた 助成 金額

２５５万円

使 用 し た 助成 金額

２５５万円

返納すべき助成金額０円
交通運賃（航空運賃＋その他運賃）： 8１万円
宿泊料： １7４万円

会 計 報 告助成金の使途内訳(使用旅費の内容)

成果の概要 / 新熊亮一
2009 年 9 月 20 日
1. はじめにアメリカ合衆国ニュージャージ州立 Rutgers 大学は 1766 年に設立されたアメリカで 8 番目に古く，州では 2 番目に古い大学である．Rutgers 大学はニュージャージ州で最も大きく，
New Brunswick 市と Piscataway 市にまたがって，4 つのキャンパスを有している．報告者
が研究を行った WINLAB (Wireless Information Network Laboratory) は，通信ネットワー
ク工学に関する大学所属の研究所としては世界でも最大規模の研究所である．約 20 人の教授陣と約 10 人のスタッフで研究教育体制を整えている．教授陣は所長の Raychaudhuri 教授をはじめとするネットワークのエキスパートから，アルゴリズム，数理モデル，セキュリティ，電波伝搬のエキスパートまで無線通信の研究を行うのに必要なエキスパートがそろっており，
プロジェクトごとにチームを組んで研究開発を遂行している．現在の主なプロジェクトは，
Dynamic Spectrum Access 技術をはじめ，Future Internet 技術，ワイヤレスセキュリティ技術，車々通信技術である．また，WINLAB は 400 という数の無線基地局をグリッド上に並べた ORBIT と呼ばれる汎用無線テストベッドを有しており，コンピュータ上の評価では見ることのできない現象をとらえることを目的としながらも，シミュレータのような操作で考案した方式を組み込むことも可能にしている． また，20〜30 人の博士課程の学生が在籍しておりプ
ロフェッショナルな意識で勉学と研究に取り組んでいる．
2. 研究成果 1「Bandwidth Exchange： コグニティブ無線環境におけるユーザ協力中継のためのインセンティブメカニズム」
無線ネットワークにおいて，ユーザ協力中継は有効な通信品質改善手法の 1 つとして期待されている．しかし，ユーザが他ユーザのデータを中継するインセンティブは保証されていない．
従来の仮想通貨や評判システムなど近代経済を模擬したメカニズムには複雑さの点で問題があった．そこで原始的な「物々交換」に着目し，無線ネットワークにおいて周波数帯域を交換する Bandwidth Exchange (BE)を提案した．公平なインセンティブを保証するため，交渉ゲーム理論の最適解であるナッシュ交渉解（NBS）を導入し，それに基づいた協力中継のアルゴリズムとプロトコルの設計を行った[1]．その際，3 人以上の交渉が複雑化する問題を回避するため，2 人 1 組の交渉アルゴリズムを 3 人以上に適用できるよう拡張した．また，Altruistic（利他的），Myopic（近視的）という人の自然な行動をベースに比較方式を考案した．これらの方式をシミュレーションに実装し，比較評価の結果から，提案方式が，高い周波数利用効率を保ちながら公平にインセンティブを割り当てられること，さらに BE なしの場合に比べ 6dB（4 倍）もの送信電力の低減を実現することを示した[2]．なお，BE は，第 4 世代携帯電話（4G）で使用される予定の OFDMA や SC-FDMA といった直交周波数分割方式をプラットホームとして実現可能で，4G での採用も視野に入れた実装実験が ORBIT を用いて始められている．

1

3. 研究成果 2「コグニティブ無線ユーザのためのコンテンツ配信システム」
WINLAB の提唱する CNF（Cache-aNd-Forward）ネットワークは，モバイルユーザがOpportunistic に断続的接続を繰り返すコグニティブ無線環境でのコンテンツ配信に最適化された，インターネットに代わる新世代のアークテクチャである．その特徴は End-to-End ではない Hop-by-Hop の転送とルータによるネットワークキャッシングであり，これらによって断続接続するユーザに対し低転送コストで大容量コンテンツを配送する．我々は特に，モバイ
ルユーザが受信完了前に切断してしまう問題を取り上げ，有効なコンテンツキャッシング法について検討した[3]．また，ここで扱うコンテンツはユーザ固有のコンテンツである．共有コ
ンテンツについては，人気度に基づいた手法がすでに多く提案されている．固有のコンテンツを前提としているため，新たなコンテンツが到着すると，LRU (Least Recently Used)にした
がって最も古いものが捨てられる．このようなキャッシュメカニズムでは，ルータごとのコンテンツ保持時間（キャッシュから廃棄までの時間）の情報を活用しやすい．まず，我々は，断続接続ユーザの転送コストの最小化を最適化問題として定式化した．その定式を基に，コンテンツ保持時間情報を用いた複数のヒューリスティック手法を提案し，比較評価からそれらの有効性を示した．さらに，このようなキャッシュが限られた資源であることを指摘し，通信帯域と同様，キャッシュ容量もが課金されるモデルの提案を行った[4]．キャッシュ容量を仮想通貨で価格付け（Pricing）し，多く仮想通貨を支払うユーザほど転送コストの大きな削減を期待できるサービスを考案し，ヘッダ構造まで含めたアーキテクチャを設計した．また，価格付
けポリシーがネットワークに与える影響についても調査した．以上の技術は CNF ネットワー
クのみならず，Hop-by-Hop を前提とした現行の CDN（Content Delivery Network）や Webにも広く適用可能である．
謝辞
共同研究を通じて有意義な討論と助言を行ってくださった Raychaudhuri 教授，Yates 教授，
Mandayam 教授をはじめとする WINLAB の皆様，京都大学教育研究振興財団をはじめ本研究を支援してくださったすべての皆様に心より感謝申し上げる．
発表文献[1] D. Zhang, R. Shinkuma, and N. Mandayam, ``Bandwidth Exchange for Enabling
Forwarding in Wireless Access Networks," IEEE PIMRC, P5-18, Sept 2009.
[2] D. Zhang, R. Shinkuma, and N. Mandayam, ``Bandwidth exchange: An energy
conserving forwarding mechanism for FDMA networks," IEEE Trans. WirelessCommunications.（査読中）[3] R. Shinkuma, S. Jain, and R. Yates, ``Network Caching Strategies for Intermittently
Connected Mobile Users," IEEE PIMRC, C8-3, Sept 2009.
[4] R. Shinkuma, S. Jain, and R. Yates, ``Personal Caching Network Service Pricing forIntermittently Connected Mobile Users," ACM MobiCom/MobiHoc.（投稿予定）
2

Bandwidth Exchange for Enabling Forwarding in
Wireless Access Networks
Dan Zhang∗, Ryoichi Shinkuma∗† and Narayan Mandayam∗∗ WINLAB, Rutgers University

671 Route 1 South, North Brunswick, NJ 08902
Email: {bacholic, shinkuma, narayan}@winlab.rutgers.edu† Graduate School of Informatics, Kyoto University
Yoshida-honmachi, Sakyo-ku, Kyoto, 606-8501, Japan
Email: shinkuma@i.kyoto-u.ac.jp
Abstract—Cooperative forwarding in wireless networks has
shown to yield benefits of rate and diversity gains, but it needs
to be incentivized due to the energy and delay costs incurred byindividual nodes in such cooperation. In this paper we consider an
incentive mechanism called Bandwidth Exchange (BE) where thecooperating nodes flexibly exchange the transmission bandwidth(spectrum) as a means of providing incentive for forwarding
data. The advent of cognitive radios with the ability to flexibly
change their carrier frequency as well as their transmission
bandwidth makes this form of incentive particularly attractive
compared to other incentive mechanisms that are often based on
abstract notions of credit and shared understanding of worth.
Specifically, we consider a N -node wireless network and use aNash Bargaining Solution (NBS) mechanism to study the benefitsof BE in terms of rate and coverage gains.

1. Each node is assigned a nonoverlapping, hence orthogonal
bandwidth Wi . The transmission power Pit for each node isfixed. The minimum required rate for each node is Rimin . We
assume an ergodic fading model where the transmission is slotted and the channel gain ρij (= ρji ) in each slot is quasi-staticand is an independent realization of a random variable (withmarginal distribution p(ρij )). To avoid confusion, subscript ij
always implies the direction from i to j. If such a subscript
is used in a transmission scheme, it is understood that i is thesource and j is the forwarder (or the AP if j = 0).
32
1
4

I. I NTRODUCTION

Consider N nodes (labeled 1, 2, . . . , N ) communicating toan access point (AP, labeled as node 0) as shown in Fig.

0 (AP).

.

II. S YSTEM M ODEL AND BANDWIDTH E XCHANGE..

..

Cooperative forwarding is an essential technique to enhanceconnectivity and throughput for wireless networks. However,forwarding always incurs some sort of cost – either real costs
like energy and power, or opportunistic cost like delay. To
circumvent the above difficulties, we have recently proposed
Bandwidth Exchange (BE) as an incentive for forwarding.
Specifically in [1], we have considered a two-node network
where each node is endowed with orthogonal frequency resources and shown that a Nash Bargaining Solution (NBS)
based mechanism can provide incentive for forwarding. In thispaper we consider the extension of BE to a N -node network,i.e., whenever a node asks another node for cooperation, itdelegates a portion of its frequency resource to the forwarderas immediate compensation for the forwarder’s cost. A similar
NBS-based cooperation strategy for a two-node network wasalso discussed in [2]. Recent advances in cognitive radio havemade this approach feasible. In particular, OFDMA (Mobile
WiMAX) [3] and SC-FDMA (LTE) [4] technologies allow
nodes to flexibly acquire and relinquish a number of the subcarriers/subchannels. Such spectrum agility achieved in radio
technology has great promise to cope with the forwarding
incentive problem that is studied in this paper.

j···iFig. 1.

···
N

Nodes connect to AP through cooperative forwarding.

In every slot a node i first attempts to transmit directly
to the AP. If the direct link is under outage, i.e., the link
capacity is smaller than the minimum required rate of node i,it tries to find a node j which could help forward its data toAP, by means of BE. During transmission, node i makes useof its available bandwidth up to Wi as dictated by BE. The
insfrom node i to node
instantaneous direct link capacity Rij
j in a slot is a function of node i’s available bandwidth andρij with transmission power Pit a fixed parameter. We assume
there is no flow splitting and every forwarder serves at mostone source.
The basic idea of cooperation through BE is the source
delegating a portion of the frequency band to the forwarderin exchange for cooperation that guarantees the minimum
required rate of the source. When node i transmits to the
AP directly, the resulting (noncooperation) rate is denoted asins(Wi , ρi0 ). When node j forwards data for node i
Rin = Ri0rsthrough BE, the resulting rate for j is denoted as Rij
and Rij

j will choose to cooperate with a nonzero probability to be
discussed shortly.
The utility function uins
ij of a stage game for an arbitrary
node j, called instantaneous rate gain, is defined to be therate increase achieved in that slot compared to noncooperation.
Instantaneous rate gain is closely related to the strategy a nodetakes. For example, the instantaneous rate gain of node j when
it chooses to forward for node i is

0 (AP)

j

Wj + ΔWij

ΔWij

iFig. 2. When the direct link is under outage, node i tries to solicit cooperation
by delegating ΔWij to node j.

s
for the source node i. Note that Rij= Rimin since a source
only seeks to maintain the minimum required rate to connect
to AP. Therefore, as shown in Fig. 2, the source node i canwithhold Wi − ΔWij and delegate ΔWij to the forwarder jsuch that(1)

Node j, in addition to guaranteeing Rimin for node i, uses theremaining capacity achieved with increased bandwidth Wj +ΔWij for its own data,
r
ins
Rij
= Rj0
(Wj + ΔWij , ρj0 ) − Rimin .

(2)

Equations (1) and (2) define the basic mechanism of BE
as described in [1] – instead of raising transmission power,
cooperation is achieved by autonomously reallocate bandwidth
resources among the nodes. Note that they also describe therelationship of the rates (Rij ) and bandwidth portion (ΔWij )to the link gain ρij . For simplicity in notation, we suppress
the explicit dependence. Link ij is considered as under outage
when it is too weak,
ΔWij < 0

(3)

min
uins
i = Ri .

(6)

The utility function of the repeated game for an arbitrary
node j is the average rate gain. A trivial stage game for node j
is one in which every decision involving j, no matter whether
it is the source or forwarder, is trivial, then uins
j = 0 for thatstage. Therefore we focus only on nontrivial stage games anddisregard, for each node j, those stage games that are trivial toj. In other words, in each nontrivial stage game of j, either j
is a source and sends a supportable request to some node i, or
j is a potential forwarder and receives a supportable requestfrom some node i.
A. Simplified N -Node Bargaining and Selection Policy
In a two-node network, a nontrivial stage game consistsof either node 1 sending a supportable request to node 2, ornode 2 sending a supportable request to node 1. Suppose thetwo events happen with probability P12 and P21 , respectively.
A potential forwarder thus has two possible strategies: C forcooperation and N for noncooperation. The two-node NBS
cthat node 2 chooses C(see [1]) tells us the probability P12cand the probability P21 that node 1 chooses C. Let v1 , v2
denote the average rate gains of node 1 and 2, respectively,
in a nontrivial stage game. Further, let λ1 , λ2 , λ3 , λ4 denote the mixing probabilities corresponding to joint strategies
N, C, C, C, C, N , N, N . The NBS is given as
maximize

v1 v2 ,

subject to

v1 = λ1 P21 R2min + λ2 (P21 R2min +P12 u12 )+ λ3 P12 u12 + λ4 · 0,λ1 ,λ2 ,λ3 ,λ4or when it leads to outage for the forwarder,r
Rij< Rjmin .

(5)

while

Wi − ΔWij

ins
Rimin = Rij(Wi − ΔWij , ρij ).

ins
r
n
uins
j = uij = Rij − Rj ,(4)

In either case, we also say the request from i is not supportable
at j.
III. C OOPERATION F ORWARDING I NCENTED BY BE
In a fading environment, the role of a node as a forwarderor source can change from slot to slot. The decision made ina slot should take the consequences it entails in future slots
into consideration. This situation is better modeled with an
infinitely repeated game [1] [5], each slot corresponding toa stage game. A node i under outage in a slot will request
for cooperation through BE; a potential forwarder j has tomake a decision from a binary strategy space, i.e., to cooperate
or not. Node j will make a trivial decision to simply rejectcooperation if the request is not supportable. Otherwise node(7)

v2 = λ1 P21 u21 + λ2 (P12 R1min +P21 u21 )+ λ3 P12 R1min + λ4 · 0,
λ1 + λ2 + λ3 + λ4 = 1,
λi ≥ 0,i = 1, 2, 3, 4.

Then, the desired cooperation probabilities arec
P12= λ1 + λ2 ,c
P21
= λ2 + λ3 .

(8)In the case of a N -node network, formulating the N -node NBS
is practically infeasible. One reason is that the strategy spacefor each node contains an exponentially increasing number ofstrategies relative to the number of nodes. This prompts us tolook for approximate solutions with much lower complexity.

One such solution is based on restricting cooperations to twohop forwarding. In other words, every node can reach the
AP via at most one other node. Since we have required one
forwarder for one source and no flow splitting, eventually
cooperation happens only between a distinct pair of nodes.
It is then natural to approximate the N -node bargaining witha series of two-node bargainings, each completely disregarding
the existence of other nodes and their influence. Consequently,
the simplified N -node bargaining boils down to every node
under outage in a slot carrying out independent two-nodebargainings with every other node according to the two-node
NBS given in equation (7).
However, with this simplification, a potential forwarder
may receive multiple cooperation requests while a source
may receive multiple positive acknowledgements. A natural
choice is to dictate that one of the source nodes is chosen
by the forwarder with a probability proportional to the corresponding cooperation probabilities calculated from the twonode NBS in equation (7). Specifically, suppose the requests
from i1 , i2 , . . . , ik are all supportable at forwarder j and thecorresponding cooperation probabilities calculated from thetwo-node NBS are Pic1 j , Pic2 j , . . . , Pick j , then j chooses tocooperate with i (1 ≤  ≤ k) with probability
Picj =

Pic j.
Pic1 j + Pic2 j + · · · Pick j(9)On the other hand, a source may also receive positive responses from multiple forwarders. The source then randomly
chooses one to follow as every forwarder equally guarantees
the minimum required rate of the source. It is possible for theforwarders whose offers are turned down to pick up requests
from other sources that they can help but we do not pursue
this situation and instead simply assume this concludes thebargaining phase of the slot. Nodes then use the remaining
time of the slot to either cooperate, or to transmit on theirown, or to stay off connection.
IV. N UMERICAL R ESULTS
A. Simulation model
Our mechanism is applicable to any multihop network,
infrastructured or ad hoc, in a licensed or unlicensed band.
For the purpose of illustration, we consider an OFDMA[3] transmission scheme much like the one used in mobile
WiMAX [6]. The presence of orthogonal subcarriers in an
OFDMA system provides a natural platform for implementing
BE by exchanging orthogonal frequency bands.
We simulate a slotted system using parameters that are
typical to mobile WiMAX. Each node is pre-assigned 20dBm
fixed transmit power [7] [8] and 500kHz transmission bandwidth corresponding to 50 subcarriers at 10kHz spacing.
When a node delegates bandwidth, it transfers a number ofthe subcarriers to a forwarder. Since nodes in our network
use mutually orthogonal portions of frequency, we model
the instantaneous capacity of link ij using its information-

theoretic rateins
(W, ρij ) = W log2
Rijρij Pit1+,Wi, j = 0, 1, . . . , N.
(10)

Links are under independent Rayleigh fading and the link gainin each slot is an independent realization of a Rayleigh randomvariable. Equivalently, this implies that ρij is exponentiallydistributed


1
ρij
exp −
p(ρij ) =
(11)
ρ̄ij
ρ̄ij
where the statistical mean ρ̄ij is given by the path loss modelρ̄ij = κd−3 ,(κ = 6 × 106 MHz · m3 /mW).

(12)

The above simulation model implicitly assumes that the
average rate of a transmission is one that is obtained when
all the subcarriers used undergo identical fading. This isdone for the simplicity of illustration but the idea of BE
and its applicability to frequency selective OFDMA systems
is still valid. The pairwise NBS with BE in equation (7) is
implemented for the above channel model. We simulate forsufficiently many slots to assess the average performance.
B. A Three-Node Example
We first present a three-node example to show the power of
BE with NBS in improving coverage and rate. Suppose node
1 is fixed at (-450m, 0) and node 2 at (450m, 0). Node 3
is allowed to vary its location in a 2000×2000m2 region asshown in Fig. 3.
If we set the minimum required rate for each node to
700kbps and the tolerable outage probability to 10%, Fig.
3(a) shows coverage area for node 3 without cooperation. Fig.
3(b) shows the improvement in coverage area achieved whenusing BE with NBS for the same level of outage. Fig. 3(c)shows a comparable coverage area for node 3 in the absenceof cooperation. However, the minimum required rate now has
to be lowered to 300kbps to generate an identical level ofoutage. This simple illustration indicates that BE can be used
to either increase coverage, or increase the supported rate.
C. Performance Evaluation in a N -Node Network
In this section, we present a comparative evaluation of
BE with NBS with noncooperation, as well as with a simple heuristic cooperative forwarding scheme. Specifically, thesimple heuristic requires that in each slot, every potential
forwarder tries to cooperate with a supportable source (seeequations (3) and (4)) randomly and the source also randomly
follows a cooperating forwarder. This is equivalent to setting
Pijc = Pjic = 1 in the NBS. Recall that every node has
its own bandwidth. When a node under outage cannot get
any cooperation its bandwidth will go unused in that slot.
The simple heuristic is a straightforward measure to reduce,
if not minimize, such waste. Therefore it serves as a goodbenchmark for the average rate gain and spectral efficiency to
be addressed.

1000

1000

1000

500

500

500

0

1

AP

0

2

−500

−1000
−1000

AP

1

0

2

−500

−500

0

500

1000

−1000
−1000

1

AP

2

−500

0

500

−500

−500

(a)

0

500

−1000
−1000

1000

(b)

1000

(c)

Fig. 3. Improvement in coverage and rate – P3out < 0.1 in the white area. (a):noncooperation, Rmin
= 700kbps; (b):BE with NBS, Rmin
= 700kbps;
ii=
300kbps;
i
=
1,
2,
3.
(c):noncooperation, RminiFig. 4.

Average rate gain in a cell consisting of varied number of nodes.

Fig. 5.

Spectrum efficiency per node.

As mentioned earlier, we simulate a slotted system that uses
parameters typical to mobile WiMAX. We consider up to 20
nodes randomly placed in a cell with a radius of 1000m. Our
results are obtained by averaging over multiple time slots andlocation instantiations of mobiles. Specifically, we look at the
metrics of average rate gain, spectrum efficiency and fairness
as a function of the number of nodes in the system.
1) Average Rate Gain: Fig. 4 shows the average rate gain
available to any node in a cell when the minimum required
rate is set to 700kbps. No matter which algorithm is used, theaverage rate gain is an increasing function of the number nodes
in the system, illustrating the benefits of user cooperation
diversity. The simple heuristic exhibits the best performance
thanks to its generous nature, though only the nodes far awayfrom the AP are the real beneficiaries while nodes close to the
AP usually suffer substantial loss while forwarding for others.

with each other. However, the spectrum efficiency per node
increases with the number of nodes. Noncooperation performs
well below the two cooperative strategies. It is noteworthy thatBE with NBS has almost the same spectrum efficiency withthe very generous simple heuristic algorithm.
3) Geometric Mean of Rate Gains: The NBS does nottake average rate gain or spectrum efficiency as an explicit
optimization objective. Rather, it provides a proportionally fairrate allocation, i.e., it tries to maximize the product of rate
gains, or equivalently, the geometric mean of rate gains. In
this sense, the geometric mean of rate gains can be regarded
a measure of the average amount of individual incentive thata node has for cooperation when BE is used with NBS. Let I
denote the fairness metric defined as
1/N
N

max(ui , 0)
.
(13)
I=

2) Spectrum Efficiency: Fig. 5 shows the spectrum efficiency averaged over the number of nodes to illustrate theeffect of user cooperation diversity when the minimum required rate is set to 700kbps. Note that in our model, nodes are
employing orthogonal subcarriers and hence do not interfere

The implication is that for fair cooperation schemes, theaverage rate gains are always positive and equation (13)reduces to the canonical geometric mean as an average amountof individual incentive. When the average rate gains for somenodes are negative, then equation (13) indicates I = 0, i.e., the

i=1

I

wireless network and used a Nash Bargaining Solution to
study the benefits of BE in terms of rate and coverage gains.
Further, the NBS also assured that the rate allocations were
proportionally fair.
While the results presented here showed the benefits of
BE as an incentive mechanism, an interesting and important aspect of BE is the need for a distributed protocol for
implementing the NBS strategy in a N -node network. The
choices of selection policies as well as other heuristic BE
based incentive mechanisms also need to be considered. These
will be discussed in an upcoming paper [9].
ACKNOWLEDGEMENT

Fig. 6.

Geometric mean of rate gains as a measure of fairness.

scheme is unfair. Fig. 6 shows I as a function of the numberof nodes when the minimum required rate is set to 700kbps.
We observe that, as a proportionally fair cooperating scheme,
BE with NBS performs desirably and the average amountof individual incentive increases with the number of nodes.
This observation is consistent with user cooperation diversity
increasing with the number of nodes. On the contrary, thenoncooperation scheme has I = 0. The simple heuristic can be
unfair as well. In fact, our experiments reveal in roughly 20%
of simulation trials, one or more nodes experience negative
rate gains.
V. C ONCLUSION AND D ISCUSSIONSIn this paper we discussed a cooperative forwarding incentive mechanism called Bandwidth Exchange where relay nodes
forward data in exchange for bandwidth that is delegated bysource nodes. The advent of cognitive radios with the ability
to flexibly change their carrier frequency as well as their transmission bandwidth makes this form of incentive particularly
attractive. Further, the use of OFDMA or SC-FDMA based
access allows for the flexible exchange of frequency bands
among the nodes. Compared to other incentive mechanisms
such simple bandwidth delegation provides more tangible andimmediate incentive. Specifically, we considered a N -nodeThis work is supported in part by the NSF under grant
number CCF-0634973 and CNS-0721826. The work is also
supported in part by Japan Society for the Promotion of
Science (JSPS) under Grant-in-Aid for Encouragement ofYoung Scientists (B) (no. 21760288).
R EFERENCES[1] D. Zhang, O. Ileri, and N. Mandayam, “Bandwidth exchange as anincentive for relaying,” in 42nd Annual Conference on Information
Sciences and Systems (CISS), Princeton, NJ, March 2008, pp. 749–754.
[2] Z. Zhang, J. Shi, H.-H. Chen, M. Guizani, and P. Qiu, “A cooperation
strategy based on Nash Bargaining Solution in cooperative relay networks,” IEEE Trans. Vehicular Technology, vol. 57, no. 4, pp. 2570–2577,
July 2008.
[3] H. Yin and S. Alamouti, “OFDMA: A broadband wireless access technology,” in IEEE Sarnoff Symposium, 2006, pp. 1–4.
[4] F. D. Calabrese, M. Anas, C. Rosa, P. E. Mogensen, and K. I. Pedersen,“Performance of a radio resource allocation algorithm for utran lte
uplink,” in IEEE VTC, April 2007, pp. 2895–2899.
[5] D. Fudenberg and J. Tirole, Game Theory. MIT Press, 1991.
[6] “IEEE standard for local and metropolitan area networks part 16: Airinterface for fixed and mobile broadband wireless access systems amendment 2: Physical and medium access control layers for combined fixed
and mobile operation in licensed bands and corrigendum 1,” IEEE Std
802.16e-2005 and IEEE Std 802.16-2004/Cor 1-2005 (Amendment andCorrigendum to IEEE Std 802.16-2004), pp. 0 1–822, 2006.
R
announces first certified MIMO 2.5GHz[7] “WiMAX Forum
mobile WiMAX products,” June 2008, [Online]. Available:
http://www.wimaxforum.org/news/pr/view?item key=cffca4e77e1900b8
fa727fe754a60be0db849e6.
[8] “XOHM ExpressCard,” [Online]. Available: http://www.xohm.com/en US/shop/devices/pccard-samsung-swce100.html.
[9] D. Zhang, R. Shinkuma, and N. Mandayam, “Bandwidth exchange:
An energy conserving forwarding mechanism for FDMA networks,” (inpreparation).

Network Caching Strategies forIntermittently Connected Mobile Users
Ryoichi Shinkuma∗† , Shweta Jain∗ , and Roy Yates∗∗ WINLAB, Rutgers University

671 Route 1 South, North Brunswick, NJ, USA 08902-3390 shinkuma,sjain,ryates@winlab.rutgers.edu† Graduate School of Informatics, Kyoto University
Yoshida-honmachi, Sakyo-ku, Kyoto, Japan 606-8501 shinkuma@i.kyoto-u.ac.jp

Abstract—This paper presents an evaluation of in-network
caching strategies for efficient delivery of content to mobile
devices that are intermittently connected to the network. Placement of content into in-network caches is formulated as an
optimization problem that minimizes access latency under certain
cost constraints. Several heuristic solutions (longest lifetime, split& longest lifetime and proportional probability to lifetime) areinvestigated via numerical examples and simulations. The results
show that the proposed methods offer significant performance
improvement over random caching and can approach the performance of exhaustive caching at every node with reduced storage
cost.

I. I NTRODUCTION
Mobile content delivery is an important technical challenge
for the next decade as more and more applications movefrom desktop computers to portable devices. Content delivery
to mobile devices is more difficult because of fundamental
limitations in coverage and bit-rate of the mobile/wirelessaccess network. Conventional services over cellular networks
are feasible but suffer from capacity limitations and corresponding high cost of delivery [1]. This has motivated theuse of opportunistic/hybrid networking in which users may
migrate between different radio access technologies such as
cellular and WiFi and may also be entirely disconnected attimes. Delivery of content to intermittently connected wirelessusers has been proposed in earlier work on Infostations [2],and more recently in context of DTN’s [3] and clean-slate
mobile internet solutions such as CNF [4]. Use of such opportunistic/disconnected networking techniques offers significant
cost/performance advantages over conventional cellular service
and is expected to become increasingly important as mobile
data applications continue their rapid growth.
Content caching is a key enabling technology for the opportunistic mobile data delivery scenario under consideration. Innetwork caching has been shown to provide large performancegains in the wired Internet [5], and is even more importantwhen designing a system for mobile data. Intermittent network
access implies that the point of attachment of a mobile end
user may vary widely with time, so that placement of the cacheneeds to consider mobility patterns as well as the anticipatedlatency and capacity. Particularly we need to deal with situations in which the end user becomes disconnected while thecontent is in transit. In this paper, we focus on the specificproblem of optimizing cache locations for mobile data where

the requester has been disconnected before delivery of thecontent is completed. The system model under consideration
is based on reliable hop-by-hop transport between in-network
caches rather than on end-to-end TCP streaming of the content
file. This model corresponds to an overlay cache network
as in CDNs [6] or integrated in-network caching as in thecache-and-forward (CNF) architecture [4]. Under hop-by-hoptransport, a file that is enroute to a mobile is temporarily
cached at all nodes along the route. So, our goal in thispaper is to determine an appropriate cache placement strategy
which takes into account content-lifetime, which is definedas the time duration from the time the content is cacheduntil it is discarded from the cache. Content lifetime may be
calculated at every node as a historical moving average ofthe time difference between caching and discarding contents
at the node. Earlier work on content caching algorithms has
focused on web caching, P2P content sharing and ad hoc
networks[7][8], but much of the discussion has been limited toplacement of content based on popularity rather than to serve
future access by a temporarily disconnected mobile user.
In the rest of this paper, we briefly review the system architecture and give our model assumptions. We then formulate
the content placement problem as an optimization problem.
When the mobile becomes disconnected, the key questionis which nodes along the route should continue to keep thecontent. The key idea is to use content-lifetime information.
Then, we propose three heuristic strategies using estimatedcontent-lifetime information. Numerical performance evaluation results are given to show that the proposed heuristics
achieve excellent performance relative to random caching andalso closely approach the performance of exhaustive cachingat every node along the route.
II. S YSTEM MODEL
Our system model is illustrated as Fig 1, in which each nodeis assumed to have a large storage cache that can be used tostore files in transit, as well as to offer in-network caching ofcommon content. Each content file transported is carried ina strictly hop-by-hop fashion. The file is transported reliably
between data stores at each node before being prepared for the
next hop towards its destination. This network corresponds
to an infrastructure part of CNF [4] and an optional formof the overlay CDN proposed in [6]. The recent reduction

Fig. 1.

System model.

Fig. 2.

Problem modelof storage cost has made this type of architecture with innetwork storage feasible. Such a network can be built on
top of IP using overlay content delivery routers connected by
IP tunnels, or as a clean-slate implementation such as CNF
described in [4]. In both cases, content delivery routers will
have additional protocol support for naming and resolutionof content files, as needed to support storage and caching
functions. In the CNF architecture, this is achieved by the“content name resolution service (CNRS)” protocol which
maintains the mapping between content ID’s and the storage
locations within the network. In such a network, when a user
requests a particular content ID, the query is resolved by the
CNRS (which in general, returns multiple router and server
addresses), and the content is then fetched from the nearest
location according to the routing metric. In order to deal withuser mobility, an additional concept of “post-office (P.O.)” isintroduced. The P.O. is responsible for maintaining pointers
to content in transit being delivered to a mobile device during
disconnections. Overall, these content management protocols
make it possible to support caching of both popular content
and content addressed to individual mobile users. In the restof this paper, we focus on content caching algorithms withthe understanding that in-network storage and retrieval is
supported by a suitable protocol similar to CNRS used in the
CNF architecture.
III. M ODEL ASSUMPTIONS
Figure 2 illustrates the model we assume in this paper.
Each node has cache function with storage capacity and serves
wireless connectivity to user terminals. The problem scenarioof this paper is described as follows:
1) The requester (user terminal) requests a file from the source
node. We assume that the requested file here is always low
popularity common content or unique personal content for therequester. We do not take into account popular content which
has already been considered in earlier work.
2) The file is transferred hop-by-hop along the routed pathfrom the source to the requester. Every enroute node keeps
the file in its temporary storage space.
3) Before the content reaches the requester, the mobile user
moves away from its original location and disconnects. The
last hop in Fig. 2 is the node that detected the requester’s
disconnection.

Fig. 3. Nodes sorted in ascending order of content
lifetime.

4) We limit our caching scheme to ‘enroute caching’; thecached nodes are chosen from the last-hop node and the nodes
between the source and the last-hop node.
5) The enroute nodes selected as cached nodes move thecontent data into their cache spaces, while the other enroutenodes discard the file from the temporary storage space.
6) The requester tries to retrieve the same content at a next
location. We assume that the retrieval request time and location
are random. The renewed request for content is first directedto the pointer function like P.O. in CNF which maintains apointer to the current location(s) to the cached data.
Other than enroute caching, we could use a predictive
caching approach as an alternative solution [9],[10]. The
problem in such an approach is that significant extra cost isrequired for content replacement and mobility prediction.
IV. P ROBLEM FORMULATION
We now formulate the problem of enroute caching for themobile requester. Suppose that we ideally know the content
lifetime ti at each node i, which corresponds to the durationfrom the time node i caches the content until the time node i
discards it. A node may discard certain cached content if thecache is full and it needs to make room for newer content.
First, we sort all the enroute nodes in ascending order ofti . Figure 3 shows an example with five enroute nodes. In
this example, the cached content is discarded earliest from thecache of node 1, while node 5 stores the content for longest
time among the enroute nodes. At time tk , node j(> k) still
keeps the content in the cache, while node j(≤ k) has alreadydiscarded it from the cache. In other words, for time period[tk , tk+1 ], node j(> k) is available as a candidate of cachednodes.
We are interested in evaluating network cost and latency
the requested content experiences after the requester tries toretrieve it at the new location. To simplify the problem, weconsider only the number of hopcounts as a metric because
our purpose here is to give a fundamental observation rather
than to estimate latency or network cost accurately. We could
later extend our observation to more realistic models; in the
future, we may design a more complex model, where wewould compute roundtrip time as a function of queuing delay,
bandwidth, and number of hopcounts. The expected shortest

hopcounts is given as:
n−1


Ck P (T ∈ [tk , tk+1 ])

(1)

k=0

where Ck is the shortest hop distance from the new location
to the closest node among the nodes for which the content
lifetime is greater than tk , i.e., the set of nodes in (k + 1,
k + 2, · · · n − 1); P (T ∈ [tk , tk+1 ]) is the probability that therequest will arrive within period [tk , tk+1 ].
Our objective is to find the optimal node set that minimize
this metric. To achieve that, we first think of minimizing Ck .
Ck depends mainly on which nodes are selected as cachednodes from available nodes for [tk , tk+1 ] and the new locationof the requester. As long as we can not predict the location,
what we can do is to minimize the possible hopcounts. If
we know the topology of the global network and it can beillustrated as Fig. 4, in which nodes a to e are available asa candidate of cached nodes, we could ensure the possible
number of hopcounts is equal or less than 2 by choosing nodesa, c, and e. However, when we are allowed to pick only two
nodes from them, we should choose nodes b and d to minimize
the possible hopcounts.
On the other hand, the number of selectable nodes should
be determined by a constraint of the storage cost because
the requested content here is low popularity common content
or unique personal content for the requester. When node i
consumes storage cost si to cache the content into its cache,the total storage cost for period [tk , tk+1 ] needs to satisfyi∈Ik si < θk , where Ik and θk indicate a set of the nodes determined as cached nodes and a threshold for period [tk , tk+1 ],respectively. Finally, we could obtain a set of the selected
nodes over the entire period I from I0 ∪I1 ∪I2 ∪I3 ∪· · · In−1 .
However, the storage constraint should be considered for theentire period rather than each period, meaning that the total
consumed storage-cost has to satisfy i∈I si < θ, where θ
is a threshold for the entire period. Another factor that makes
this problem difficult is P (T ∈ [tk , tk+1 ]) in Eq. (1), which isthe probability that the retrieval request arrives during period[tk , tk+1 ]. To minimize the objective function defined by thisequation, we need to make Ck smaller as P (T ∈ [tk , tk+1 ])is larger.
To motivate the above problem formulation, we draw a
representative network in Fig 4. We find two time intervals[0, tv ] and [tv , tq ] such that 0 < tv < tq and P (T ∈ [0, tv ])= P (T ∈ [tv , tq ]) = 0.5. We assume that nodes a to c
and d to e have cached copies with lifetime tq and tv ,respectively, and the requester’s position can be limited only
to leaf node Lj (j = 0 to 5). The shortest hopcount to acached location Ck when the requester connects at points L0
at time intervals [t0 , tv ] and [tv , tq ] are [1, 2]. Therefore theexpected shortest hopcount is obtained from the formulation(1) as 3/2. The expected shortest hopcounts for all locations
L0 to L5 are [3/2, 6/2, 4/2, 2/2, 2/2, 4/2]. Our objective is toselect a subset of nodes from this set such that the storage costdoes not exceed a fixed threshold and the expected hopcountis minimized. For this example we choose a storage threshold

Fig. 4.

An example of cached-node selection.

of two nodes. Given the storage constraints, the optimal cache
locations are nodes a and c.
V. H EURISTIC STRATEGIES USING CONTENT LIFETIMEINFORMATIONIn the previous section, we gave a mathematical formulation of the caching issue for intermittently connected mobile
users based on the content lifetime concept. In reality, theoptimization based on this formulation seems to be impracticalbecause we need to pick the node set minimizing the objective
defined by Eq. (1) with taking into account the global network
topology, available nodes at each period, P (T ∈ [tk , tk+1 ]),and storage constraint. However, Eq. (1) tells us that we shouldtake into account content lifetime to choose cached nodes
because nodes with longer content lifetime can reduce Ck
for many possibilities of P (T ∈ [tk , tk+1 ]). Furthermore, toreduce Ck , we need to take into account geometric positionof nodes in the network as demonstrated using an example inFig. 4 in the previous section: it is obviously ineffective tochoose the set of neighboring nodes like a and b or d ande. These observations motivated us to propose the following
three proposed strategies based the estimated content lifetime:
Strategy 1: Longest lifetime (LT)
Step 1 Initialize: set i=1 and s=0.
Step 2 Pick node with i-th longest lifetime and add it to I.
Step 3 s = s + si . si denotes consumed storage cost by node
selected at Step 2.
Step 4 If s < θ, i = i + 1 and back to step 2. Otherwise terminate
algorithm.
Strategy 2: Split & longest lifetime (SLT)Step 1 Initialize: set M =1.
Step 2 Set s=0 and split enroute network to M sub-networks withapproximately equal number of nodes in each sub-network.
Let set of split networks denote M.
Step 3 For every sub-network m ∈ M
1) Pick node with 1st longest lifetime in sub-network m
and add it to I.
2) s = s + sm . sm denotes consumed storage cost by
selected node from network m.
Step 4 If s < θ, M = M + 1 and back to step 2. Otherwise
terminate algorithm.
Strategy 3: Proportional probability to lifetime (PLT)Step 1 Initialize: set M =1.
Step 2 Pick M nodes from enrouten nodes. Node i is chosen witht ; nodes are chosen withprobability Pi = ti /j=1 jprobability proportional to their content lifetimes. Add thechosen nodes to I.
Step 3 Set s=0. For every chosen node i ∈ I, s = s + si .
Step 4 If s < θ, M = M + 1 and back to step 2. Otherwise
terminate algorithm.

We could say that LT is one of the optimal strategies because
it maximizes the expected number of remaining cached nodes.

SLT and PLT are expected to reduce the expected number ofhopcounts from the new location of the requester to the nearest
cached node. In the example of Fig. 4, LT would select two
nodes from the set [a, b, c], SLT would select a node fromthe set [a, b, c] and one from [d, e] and PLT would select two
nodes from [a, b, c] with higher probability compared to [d, e].
Therefore, in this example, LT is closest to optimal while SLT
and PLT follow closely. In order to implement these strategies,
at least one node needs to know the information of the estimated content-lifetime and the estimated storage cost for every
enroute node. One implementation strategy is for every enroutenode to attach its own estimated content-lifetime and storage
cost to the transferred data. This additional information is verysmall compared to the data size. Therefore, the overhead isinsignificant. The last-hop node would then have the necessary
information to execute the heuristic strategy. Content lifetime
may be calculated at every node as a historical moving averageof the time difference between caching and discarding contents
at the node.
VI. N UMERICAL EVALUATION MODEL
In this section, through a numerical evaluation, we provide afundamental observation for the caching issue under intermittent connectivity. Our interest here is to evaluate the decreasein experienced cost with the proposed heuristic strategies whenuser movement happens. Generally speaking, to investigate
caching schemes, we would need to introduce query model,
cache replacement policy, content-size distribution, and link
capacity model [8]. However, if we incorporate specific models
to our evaluation, the existences of alternative models andparameters might cause loss of generality. Hence, we came up
with a general model of the caching issue for intermittently
connected mobile users described as follows:
1) Generate a network consisting of a few hundreds nodes
2) Choose randomly a node as the source
3) Choose randomly the last-hop node (see Fig. 2)4) Set the content lifetime in each cached node . Note thatthe content lifetime in the source is set to infinity.
5) Apply one of the heuristic strategies to the enroute nodes
and determine cached nodes
6) Choose a node as the (future) location of the requester7) Set the request time manually8) Pick the cached nodes whose content lifetime is NOT
older than the request time9) Measure the minimum hop distance from the requester
location to the nodes picked at the previous stepThis model allows us to clearly capture how the proposed
strategies work when the requester’s movement occurs without
using any specific query and mobility models. However, itremains an issue how to appropriately model the content
lifetime of each node. We came up with a simple model, whichis represented as:(2)
ti = N̄i /λiwhere N̄i , λi , and ti are the number of content files node i canstore, how many contents arrive at node i per time unit, andthe expected lifetime of a content cached in node i. This model(a) Fixed content lifetime(b) Exponential distribution

Fig. 5. The average number of hopcounts between the closest cached nodeand the requester as a function of the request time.

is based on the assumption that nodes get an opportunity toreplace their caches every time a new content arrives at them.
This is a reasonable assumption whatever replacement policy
we use. For example, suppose that we adopt the least-recentlyused (LRU) policy [7]. The newly cached content will bediscarded at earliest after N̄i new contents additionally arrive
at node i. In our evaluation, we set N̄i uniform and content
arrival rate λi for node i proportional to how many shortest
paths between two nodes pass through the node. This setting
is also reasonable because nodes with higher centrality such astransit and junction nodes are more likely to receive contents
in enroute caching.
VII. N UMERICAL RESULTS
In this section, we compare the performance of our strategies with a simple random strategy, in which cached nodes are
randomly chosen from the enroute nodes, and the ‘every-node’strategy, in which every enroute node is chosen as cachednodes without any constraint. The latter is a lower bound toassess the optimality of strategies. As illustrated in Fig. 1, thecontent-delivery network consists of the Transit domain and
the Stub domains like the current internet. To generate thismodel, we used Georgia Tech Internetwork Topology Model(GT-ITM) [11]. We generated a simple network with twotransit nodes in one transit network, 100 nodes in each of two
stub networks. The average and maximum of shortest distance
between two nodes are 8.8 and 19. The average and maximum
numbers of degrees per node are 3.2 and 11. Although, due tospace limitations, we just show the results using this topology,
we have experimented with several other topologies and foundessentially the same results.
Figure 5(a) shows the number of hopcounts measured atstep 9 in the previous section, which was averaged over 5000
trials. Suppose that three nodes are selectable as cached nodes
in addition to the source under a storage constraint. The
horizontal axis indicates when the retrieval request arrives after
the disconnection happened at time 0. The retrieval request
time is represented using the relative value to the maximum
content lifetime which is set to 1000. In Fig. 5(a), the later
the retrieval request arrives, the larger number of hopcounts

Finally, we evaluate the average number of hopcounts asa function of the number of selectable nodes shown in Fig.
7. As the number of selectable cached nodes increases, all
the strategies become closer to the Every-node strategy as
we could easily predict. We observe that the superiority of
SLT to PLT decreases as the number of the selectable nodes
increases. LT minimizes the number of hopcounts regardlessof the number of selectable nodes.
Fig. 6. The cumulative distribution function of the number of increased
hopcounts compared with the Every-node strategy. The request time is 20.

Fig. 7. The average number of hopcounts vs. the number of selectable nodes.
The request time is 200.

is observed. This is simply because the number of cachednodes decreases as time passes. The proposed strategies aremuch better than the Random strategy and comparable with theEvery-node strategy. Note that the worst number of hopcounts
here should be 8.8, which is equivalent to the average ofthe shortest distances between two nodes. The best one is
4.9, which we can observe when Every-node is used and therequest time is zero. The horizontal axis is scaled so as tocover this range.
In our previous result, the content lifetime was given as
modeled in the previous section. We change this model inthe following evaluations so that the content lifetime for nodei follows the exponential distribution with mean of N̄i /λi .
As shown in Fig. 5(b) even using such probabilistic lifetime
model, the proposed strategies work well. In both Figs. 5(a)and 5(b), the LT strategy is the best among the three proposed
strategies. This is simply because LT maximizes the expected
number of remaining cached nodes.
To capture the benefits of SLT and PLT against LT, weplot how many hopcounts were increased compared with theEvery-node strategy in Fig. 6. We here set the request time to
20 units of time. The result shows that when request arrives
very early, there is a one hop improvement in the performanceof SLT with respect to LT. Why the improvement was solimited is because, as the request is earlier, the number ofremaining cached nodes is larger, which makes the difference
between the two schemes small. On the other hand, when the
retrieval request arrives late, the number of remaining cachednodes reduces, resulting in the loss of the benefit of SLT.

VIII. C ONCLUSION
In this paper, we have discussed network caching strategies
for intermittently connected mobile users. We showed the
problem formulation and then proposed heuristic strategies
based on the content lifetime concept. Through a numericalevaluation, the proposed heuristic strategies were shown toprovide significant performance improvement over random
caching and also approach the lower bound for enroutecaching. Considering the complexity, we could conclude thatcomplexity of an optimization solution is unnecessary. Furthermore we observed the LT strategy, which simply chooses
the nodes with the longest lifetime, minimized the hopcounts
because this is the optimal solution to maximize the expected
number of remaining cached nodes for the future retrieval
request. Since we have given a general performance study inthis paper, future work should include consideration of more
specific network, traffic and mobility models. We could further
extend our discussion to predictable mobility and request time
though we assumed only unpredictable ones in this paper.
Prototyping of mobile content caching algorithms is also underconsideration at WINLAB using the ORBIT radio grid testbed[12] as the experimental platform.
ACKNOWLEDGMENT
The authors wish to thank Dr. Dipankar Raychaudhuri (WINLAB,
Rutgers University) for his great advices on this paper.

R EFERENCES[1] W. Y. Ma et al., “A framework for adaptive content delivery in heterogeneous network environments,” MMCN, 2000, pp.86-100.
[2] R. H. Frenkiel et al., “The infostations challenge: Balancing cost andubiquity in delivering wireless data”, IEEE Personal Commun., April
2000, pp. 66-71.
[3] K. Fall, “A Delay-Tolerant Network Architecture for Challenged Internets,” Applications, Technologies, Architectures, and Protocols for
Computer Communication, Aug 2003, pp.27-34.
[4] S. Paul et al., “The cache-and-forward network architecture for efficientmobile content delivery services in the future internet,” Innovations in
NGN: Future Network and Services, K-INGN, May 2008, pp.367-374.
[5] J. Dilley et al., “Globally distributed content delivery,” IEEE Internet
Computing, Vol. 6, Issue 5, Sept 2002, pp.50-58.
[6] S. Ganguly et al., “Fast replication in content distribution overlays,” IEEE
INFOCOM, Vol. 4, Mar 2005, pp.2246-2256.
[7] A. Wierzbicki et al., “Cache replacement policies revisited: the case of
P2P traffic,” IEEE CCGrid, April 2004, pp.182-189.
[8] L. Yin and G. Cao, “Supporting cooperative caching in ad hoc networks,”
IEEE Trans. on Mobile Computing, Vol. 5, Issue 1, Jan. 2006, pp.77-89.
[9] G. Yang et al., “Ad-hoc Storage Overlay System (ASOS): A DelayTolerant Approach in MANETs,” IEEE MASS, Oct. 2006, pp.296-305.
[10] S. Ktari et al., “Performance Evaluation of Replication Strategies in
DHTs under Churn,” ACM MUM, Dec 2007, pp.90-97.
[11] K.I. Calvert et al., “Modeling Internet topology,” IEEE Commun. Mag.,
Vol. 35, Issue 6, Jun 1997, pp.160-163.
[12] http://www.orbit-lab.org