Joint head selection and airtime allocation for data dissemination in mobile social networks

ContentslistsavailableatScienceDirect

Computer Networks

journalhomepage:www.elsevier.com/locate/comnet

Joint head selection and airtime allocation for data dissemination in mobile social networks

Zhifei Mao

^a,∗

, Yuming Jiang

^a

, Xiaoqiang Di

^b

, Yordanos Woldeyohannes

^a

aDepartment of Information Security and Communication Technology, NTNU, Norwegian University of Science and Technology, Trondheim N-7491, Norway

bDepartment of Network Engineering, Changchun University of Science and Technology, Changchun 7089, China

a rt i c l e i n f o

Article history:

Received 29 March 2019 Revised 30 September 2019 Accepted 8 November 2019 Available online 9 November 2019 Keywords:

Mobile social networks Data dissemination Airtime allocation Fairness Game theory Nash bargaining,

a b s t r a c t

Byformingatemporarygroup,usersinmobilesocialnetworks(MSNs)candisseminatedatatoothersin proximitywithshort-rangecommunicationtechnologies.However,duetousermobility,airtimeavailable forusersinthesamegrouptodisseminatedataislimited.Inaddition,forpracticalconsideration,astar networktopologyamongusersinthegroupisexpected.Fortheformer,unfairairtimeallocationamong theuserswillunderminetheirwillingnesstoparticipateinMSNs.Forthelatter,agroupheadisrequired toconnectotherusers.Thesetwoproblemshavetobeproperlyaddressedtoenablerealimplementation andadoptionofMSNs.Tothisaim,weproposeajointheadselectionandairtimeallocationschemefor datadisseminationwithinthegroupusingNashbargainingtheory.Specifically,weconsidertwocasesin termsofuserpreferenceonthedatatobedisseminated:ahomogeneouscaseandaheterogeneouscase.

Foreachcase,aNashbargainingsolution(NBS)basedoptimizationproblemisproposed.Theexistence ofoptimal solutions to theoptimization problemsis proved,which guaranteesPareto optimalityand proportional fairness.Next,analgorithmthatallowsdistributedimplementation isintroduced.Finally, numericalresults arepresented toevaluatetheperformance,validateintuitions andderiveinsightsof theproposedscheme.

© 2019TheAuthors.PublishedbyElsevierB.V.

ThisisanopenaccessarticleundertheCCBY-NC-NDlicense.

(http://creativecommons.org/licenses/by-nc-nd/4.0/)

1. Introduction

Mobile social networks (MSNs) enable people to share con- tentandcommunicatewithoutInternetaccessbyexploitingshort- range wireless communication technologies such as WiFi Direct andBluetooth[1–3].Dueto thenatureofintermittentconnectiv- ity, MSNs are often regarded as a special type of delay tolerant networkthatutilizesopportunisticcontactsamongmobileusersto deliverdata[4–6].Nowadays,peoplearebecomingincreasinglyin- separablefromtheirportablesmartdevicessuch assmartphones.

Thisbrings numerousopportunitiesforpeopletoformtemporary groups to exchange information when their portable devices are within each other’s transmission range. In particular, MSNs are promisingcommunicationsystemsforpeopleinareaswhereInter- netaccessisunavailableortoocostly.Forexample,whendisasters strike,Internetinfrastructuresuchascellularnetworksareamong thefirst piecesofcriticalinfrastructuretofail, leavingindividuals

∗ Corresponding author.

E-mail addresses: [email protected] (Z. Mao), [email protected] (Y. Jiang), [email protected] (X. Di), [email protected] (Y. Woldeyohannes).

disconnectedfromoneanotherandfromvitalinformationsources [7]. In such scenarios, MSNswill be one of the fastestandmost handywaystoprovidedigitalconnectionamongindividuals.

Over the past years, significant MSN research efforthas been conducted. However, the main focus has been on routing, data dissemination and community detection, leaving a fundamental MSNproblemnearlycompletelyuntouched,whichislocalresource management [3]. Thissurprising phenomenon isprobablydue to thatforvarioustypesofwirelessnetworks,localresourcemanage- menthasbeenextensivelystudied,andconsequentlyonecouldex- pectthattheirexistingsolutionsmightbedirectlyappliedoreasily extendedtoMSNs.Unfortunately,thisexpectationignoresafunda- mentaldifferencebetweenMSNsandotherpopulartypesofwire- lessormobilenetworks. Thedifferenceisthat,inthelattercases, there exist base stations (BSs) or access points(APs) formobile users to get connectedto and through the Internet, and insuch cases,local resource management, e.g. scheduling the useof air- timeamongusers,typicallyimplicitlyassumesthattheBSsorAPs arealwayswillingtoserve,andhenceconsidersonlyuserdevices inmakingthedecision.

https://doi.org/10.1016/j.comnet.2019.106990

1389-1286/© 2019 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license. ( http://creativecommons.org/licenses/by-nc-nd/4.0/ )

However, inMSNs, that seemingly unquestionableassumption maynothold,particularlywhenauserneedstouseher/hissmart device to store-carry-forward data for the others [8].This is be- cause, a smart device normally has limited capacities in terms ofe.g. energy, storage, processing andcommunication. In conse- quence,localresourcemanagementinMSNsnotonlyshouldcon- siderthedevices withdata tosend orreceive,butalsomustnot forgetthehelpersthatcontributeadditionallyintermsoflocalre- sourcessuchasenergyandcommunicationtoact likeBSsorAPs tohelptheothers.ThispartlyexplainswhyresearchonMSNshas beenprogressingformorethanonedecadebutrealimplementa- tionsandadoptions of MSNsinthepublic are rarelyseen today:

Overlookingtheadditionalcostsincurredtothehelperessentially discouragesanyone tobe helper,whichisa foundationforMSNs to work. Nevertheless, the concept of MSNs has drawn huge at- tentionofindustrybesidesacademy.Recently,MozillaandtheU.S.

NationalScience Foundationhavebeenrunningacontest seeking innovativesolutionstoconnectpeoplewhoaredisconnectedfrom the Internet due to disaster or insufficient connectivity [7]. This providesagreatopportunitytoworkonthemissingpiecesinMSN researchtowards publicadoption ofMSNs,andmotives thework ofthispaper.

In thispaper,wefocus ona fundamentalprobleminlocal re- sourcemanagement, whichisairtime allocationamong usersina temporary group formed on the move, since available airtime is typicallylimitedinMSNsduetousermobilityandshorttransmis- sionrange.Theairtimerequiredfordisseminatinga pieceofdata fromitssourcetoalltheinterestedgroupmembersdependsonits communicationnetwork topology.Inthis work,we consider that eachgroup uses astar topologyto communicate whereone user is selected asgroup head to serve like a personal hot-spot open tothegroup andmanage thegroup whileother usersconnectto theheadasperipherals.¹ Such astarformissimpleyetpractical² becauseitisnativelysupported bythemostpopularoff-the-shelf short-range communication technologieson portable devices, in- cludingWiFiDirect[9]andBluetooth[10],makingtheunderlying networkfunctionalitiestransparenttoapplicationdevelopment.

Withstartopology,a groupheadmust beselectedamongthe users.Theheadneedstoforwarddatafortheperipheralusers,and thusspendsmorebatterypowerthanthem.Therefore,itisimpor- tant to encourage users to be the head. In addition, since users mayhave different battery levels and link capacities, head selec- tioniscriticalinthat itimpactsusers’utilitiesandtheamountof datathatcanbe disseminatedwiththelimitedairtime.Inthelit- erature,variousfairairtime(orrate)allocationschemeshavebeen proposedfortraditionalWLANsandcellularaccessnetworks[11–

14]. However, they all implicitly assume that the airtime islong enoughsothatallthedatatransmissioncanbefinallycompleted.

Thisassumption doesnot generallyholdinMSNswherethecon- tactdurationamongusersislimitedduetousermobilityandshort transmissionrange.Inaddition,theutilityfunctiontheyuse,which istypicallyu(x) wherexisthe allocatedairtime (orrate),cannot characterizethespecificsofusersinMSNs,includingdatadissemi- nationneed,preferenceonotherusers’dataandbatterylevel.Fur- thermore,unlikepreviouswork,thegrouphead,counterpartofAP inWLANs[14]andBSincellularnetworks[13]respectively,must alsobe a target ofthe airtimeallocation, equivalenttothe other

1Group head and peripherals are called group owner and clients in Wi-Fi Direct terminology [9] , and called master and slaves in Bluetooth terminology [10] .

2Theoretically, mesh topology is also possible for connecting MSN users in prox- imity. However, it requires additional functionalities such as multi-hop routing and topology management implemented on users’ portable devices. Similarly, while wireless channels are broadcast in nature, using it for applications usually also re- quires changes to the applications and the various layers below, to be able to make use of this feature.

Table 1 Notations.

Notation Description

G User group

N Number of users in G

N i Number of transmissions in the dissemination of i ’s data L Set of all directed links

L i Set of all the links that disseminate i ’s data ( i, j ) Link that sends data from node i to node j c ij Rate of link ( i, j )

M i Set of data that node i intends to disseminate z i Size of all the data in M i

γ Unit reward

f i Amount of data node i forwards for other nodes u i Utility of node i

v ( ·) Valuation function g ( ·) Cost function

d i Amount of data i disseminates b i Amount of data of interests i receives e i Total energy consumption of node i a i Head indicator

e ^s unit energy consumption for sending data e ^r unit energy consumption for receiving data s i Amount of data node i sends

r i Amount of data node i receives E i Energy budget of node i

δi Node i ’s sensitivity to battery power consumption x i Airtime for the dissemination of node i ’s all data x ⁱ_{k j} Airtime for link ( k, j ) in L ito disseminate node i ’s data θi Amount of data transmitted by every link in L i

αi Bargaining power of node i

x ^m_i Airtime for disseminating node i ’s data m

usersconnectingtoit.Theseaddmoredifficultyindesigningafair airtimeallocationschemeforlocaldatadisseminationinMSNs.

In thispaper, we address airtime allocation jointly withhead selectionamongagroupofusersinanMSN,which,tothebestof ourknowledge, has neverbeen considered previously.Since any- oneinthegroupmayormaynot(wantto) bethehead,agame- theoretic approachisnaturallyadopted.Specifically,we formulate the problem of joint head selection and airtime allocation as a Nash bargaininggame. An advantage ofusing Nash bargainingis that thesolution,ifitexists, isknownto be Paretooptimal,pro- portionallyfair,andacceptablebyallusers.Motivatedbythis, we provetheexistenceofoptimalsolutiontothejointheadselection andairtimeallocationNashbargaininggameusingdecomposition.

Inaddition,wepropose adistributedalgorithmforjointheadse- lection and airtime allocation, based on the decomposition idea.

Moreover,numericalresultsarepresentedtoprovideanoverview ofthe performance, validate intuitions and derive insightsof the proposedjointheadselectionandairtimeallocationscheme.

Therestofthispaperisorganizedasfollows.InSection2,we introducethesystemmodelincludingnetworkmodel,dissemina- tionmodel,incentivescheme,anduserutility function.The Nash bargaining solution (NBS)-based head selection andairtime allo- cationschemeisproposed andstudiedinSection 3.InSection4, we show the numericalresults. Section 5 presents related work.

Finally,weconcludeinSection6.

2. Systemmodel

Since there are many notations in this paper, we summarize theminTable1forreader’sconvenience.

2.1. Networkmodel

Consider a group of users (or nodes) G=

{

¹,2,...,N

}

^{in an}

MSN, whichcome intocontactby opportunity andwouldlike to disseminatetheirdatatootherinterestednodesinthisgroup.The

nodes can communicate with each other by forming a star net- work (G,L) ^where L is the set of all directed links. One of the nodesisselectedastheheadofthegroupwhileother nodes,re- ferred to asperipheral nodes,connect to each other through the head.Denote c_ij therateoflink(i, j) thatsends datafromnode i tonodej.WeassumedifferentlinksinLmayhavedifferentrates.

Inaddition,nearbygroupsusedifferentchannelsfordatadissemi- nationanddatatransmissiononeachchannelisindependentfrom theotherchannels,e.g.inWiFi-Direct.Therefore,linksinthesame group sharethesame frequencyandtheycannot transmitsimul- taneously.

2.2. Disseminationmodel

DenoteMithesetofdatathatnodeiintendstosharetoother interested nodesin the group duringthe contact (Theremay be some nodesthatdonot haveanydatatodisseminatebutare in- terestedinother nodes’data.).Giventhatthedataofaperipheral nodecaninterestmultiplenodesinthegroup,theheadcaninten- tionallystorethedata(orpartofthedata) oncereceivingitfrom thesource nodeforthefirsttime andthenforwardittothe rest recipients, so that the limitedairtime can be utilized more effi- cientlythandirectlysendingmultipletimesfromthesourcenode toeachrecipient.

2.3. Incentivescheme

Forwardingdatafortheperipheralnodeswillincurahighcost totheenergy,storage,etc.,therefore,rationalnodesarenotwilling tobetheheadandforwarddataforothersunconditionally.Toen- couragenodestobecomethehead,weassume thereisanincen- tiveschemesuchthattheforwardingbehaviorisrewardedbythe system. Notethat the peripheralusers donot haveto paytothe headforforwardingtheirdata:Inpractice,sucharewardcouldbe invariousformssuchaspopularityand/orreputationintheMSN.

Forsimplicityofanalysis,inthispaper,wedonotrestricttheform ofimplementingtherewardandusea linearabstract formofre- warding function, i.e., thenode will receivea reward of

γ

·fifit forwards an amountfofdatafor others,where

γ

^{istheunit re-}

ward.

2.4. Usermodel

Nodes are effectively autonomous agents, since there is no network-widecontrolauthority.Eachnodecandecide,onitsown will,whethertojointhegroup andcontributeresources tofacili- tatedatadissemination.Inaddition,thenodeselectedasthehead contributesmoreresources thanclientnodes.Therefore,itisrea- sonable to assume that each node seeks to maximize its utility from data dissemination over a contact. Denote u_i the utility of nodei,itisgivenbythevaluationofthedataitdisseminatesand the data ofinterests it receives, minus the energycost forsend- ing/receivingdata,plus therewardforforwardingdataforothers ifiisthehead:

ui=

v ₍

di+bi

)

−g

(

^ei

)

+ai

γ

^fi (1) where v(·) isthe valuation function, g(·) isthe cost function,d_i is theamountofdata idisseminates,b_iis theamountofdata of interests i receives, f_i is the amount ofdata i forwards for other nodesifitisthehead,e_iisthetotalenergyconsumptionforsend- ingandreceivingdata,anda_i=

{

¹,0

}

^{istheheadindicator.Forany}

node i,a_i=1meansitisselectedasthegroupheadwhilea_i=0 means itisa peripheralnode. Sincethere willbe onlyone head, we have N

i=1a_i=1. Denote e^s ande^r the unit energyconsump- tion for sending and receiving data, respectively. Then we have e_i=e^ss_i+e^rr_iwheres_iistheamountofdataitsendsandr_iisthe

Fig. 1. Differences between d iand s i, and between b iand r i. Node 3 and 4 are inter- ested in node 2’s data Aof 5 MB, but node 1 is not. Since they cannot communicate directly, node 2 will send Ato the head, i.e., node 1 first, then node 1 will forward data A to node 3 and 4. As we can see, the amount of data node 2 disseminates is d 2= 2 ×5 = 10 MB, while the amount of data it directly sends is s 2= 5 MB. For node 1, the amount of data it receives is r 1= 5 MB, while the amount of data of interests it receives is b 1= 0 MB since it is not interested in data A.

amountofdataitreceives.Toclarifythedifferencebetweend_iand s_i,andthedifference betweenb_iandr_i,an exampleisillustrated inFig.1.

Forthe valuationfunction v(·),weassume itisa strictlycon- cave, positive, and increasing function of d_i+b_i, and

v

₍·)=0 if d_i+b_i=0.Function

v

(^di+b_i)=log(¹+d_i+b_i)^{satisfiestheabove} assumptions. Such logarithmic function has been often used in the literature (e.g., [15–17]) to model a network user’s satisfac- tionorevaluationover certainnetwork resources. Fortheenergy costfunctiong(·), weassume itisastrictly convex,positive,and increasing function of e_i, and g(·)=0 if e_i=0. In addition, each node i hasan energybudget ofE_i that can be spent during the contactperiod. Clearly, we need to have e_i≤E_i. Function g(^ei)=

δ

i(E_i−¹e_i−_E¹

i)^{satisfiestheabove}assumptions,where

δ

i∈[0,1]isa normalizationparameter that indicates useri’s sensitivityto bat- terypowerconsumption³Forexample,ausermayhavehighsen- sitivitywhenbatterychargingisinconvenient.As arationalnode willnotparticipateinthegroupifitwillbecomeworse off,itre- quiresu_i≥0foralli∈G.

3. Nashbargainingtoheadselectionandairtimeallocation

Whenanumberofuserscomeintoeachother’sproximity,they create a contact opportunity to form a group to exchange data withinterestedones. Before theycan dothat, theyhaveto make a properdecision onhead selection andairtime allocation. Since theusersareautonomousandrational,eachofthemwouldliketo benefitfromthecontactby disseminatingitsdata,receiving data ofinterests,orobtainingreward.However,theairtimecanbevery limitedduetotheir mobilityso that itwould beimpossiblethat everyone gainsasmuchashe/shewants. Therefore,thefinal de- cision ofhead selection andairtime allocation should be accept- able to everyone in order to resolve conflicts of interest. Other- wise,therewouldbenoguaranteethatthegroupwillbeformed.

Forsuch bargainingproblemswhereplayersnot onlyhaveincen- tive to cooperate but also have incentive to oppose each other, Nashbargainingsolution(NBS)isan axiomaticapproachthatcan uniquely identifyan outcome by its four axioms. In thissection, weuseNashbargainingtoformulatetheproblemofairtimeallo- cationjointlywithheadselection,andanalyzetheexistenceofits optimalsolution. First ofall, we review the basics ofNBS in the followingsection.

3.1. BasicsofNashbargainingsolution

Inthissection, we briefly review the concepts andresults re- latedtoNBS.ConsiderabargaininggameofNplayerswhobargain

3This cost function is a modified version of that used in [17] which does not satisfy g(0)= 0 .

orcompeteforashareofalimitedresource(airtimeinourcase).

Throughoutthegame,theplayerseitherreachanagreementonan allocationoftheresourceorcomeintodisagreement.Letx_ibethe shareoftheresourcethatplayerigets,x=(^x1,x₂,...,x_N)^iscalled a feasible allocation. For each player i, it has a utility function u_i(^x)^: X→RwhereX⊂R^Nisthesetofallpossibleallocations.

Denoteu^d_i the utilityofplayer i whentheplayerscomeinto dis- agreement,u^d=(^ud1,u^d₂,...,u^d_N) ^iscalledthe disagreement point.

Thenabargaininggamecanbeformally givenbythepair(U,u^d) whereU isthesetofallfeasibleutilityvectorsu=(^u1,u₂,...,u_N)^. Let

ψ

^:(U,u^d)→R^N a bargainingsolutionthatassignsto the bargaininggame(U,u^d) ^{an elementof} U.

ψ

(U,u^d) ^{issaid tobe} anNBSifthefollowingaxiomsaresatisfied:

• PAR(Paretooptimality).Foranyt,t∈U,ift_i>t_iforalli,then

ψ

(U,u^d)=t.

• ILT(IndependenceofLinearTransformations).Supposethatthe game (V,v^d) ^{is obtainedfrom} (U,u^d) ^{by the} transformations

v

i=

σ

iu_i+

θ

i,

σ

i>0 forall i, then

ψ

i(V,v^d)=

σ

i

ψ

i(U,u^d)+

θ

i

foralli.

• SYM(Symmetry).IfUisinvariantundertheexchangesofplayer i andplayerj andu^d_i =u^d_j,then

ψ

i(U,u^d)=

ψ

j(U,u^d), forall possiblei,j.

• IIA (Independence of Irrelevant Alternatives). If (U,u^d) ^and (V,u^d)^{are two bargaininggames with} V⊂U and

ψ

(U,u^d)∈ V,then

ψ

(U,u^d)=

ψ

(V,u^d)^.

PARensuresnowastageintheresource.ILTstatesthatthebar- gainingsolutionisinvariantwithrespecttolinearutility transfor- mations.SYMmeansthatifanytwoplayershavethesameutility functionanddisagreementutility,they willhavethe sameutility inthe bargainingsolution. IIA says that if thefeasible utility set shrinks,butthebargainingsolutionremainsfeasibleinthesmaller set,thenthebargainingsolutiontothegamewiththesmallerutil- ityset shouldbe thesame.Thelatterthreeaxioms(i.e.,ILT,SYM andIIA)are oftenregarded asaxiomsof fairness[18,19],asthey allow NBS to select a fair allocation among the set ofall Pareto optimalallocations.MoredetailsandinterpretationsofNBScanbe foundin[20].

Assuming theutility set U is compact convex andthere is at leastone usuch thatu_i>u^d_i forall i,then thereexists aunique bargainingsolutionfulfilling theabove fouraxioms, which maxi- mizesthefollowingNashproduct(orNashwelfare)[18]:

N

i=1

(

^ui

(

^x

)

−u^d_i

)

. (2)

Thoughnoexplicitfairnessisdefinedwithinthefouraxioms,NBS showsstrongfairnessproperty.Itiswell-knownthatwhenu^d_i =0 foralli,NBSguaranteesproportionalfairness(PF)inutility.Anal- location that satisfies PF should be that, moving away fromthe PFallocation or NBS to anyother feasible allocation will not in- creasethe aggregate of proportional changes in utilities [21–23]. Inmathematicalterms,N

i=1 u_i−u_i

u

i ≤0whereu=(^u1,u₂,...,u_N) isthePFallocationandu=(^u1,u₂,...,u_N)^{isanyotherfeasibleal-} location.Duetosuchrelationship,NBSisoftenregardedasagen- eralizationofproportional fairness.Byrelaxingthe axiomofSYM [18,24],the so-calledgeneralized(orasymmetric)NBScanbe ob- tainedbymaximizing

N

i=1

(

^ui

(

^x

)

−u^d_i

)

^{αi (3)}

where0≤

α

i≤1isthebargainingpowerandN

i=1

α

i=1.General- izedNBS satisfies the axiomsofPAR, ILT andIIA andguarantees weighted proportional fairness which satisfies N

i=1

α

i·^ui_u^−ui

i ≤0

[25].

In thefollowing, wewill first elaborate theutility function of usersinthecasesofhomogeneous userpreferenceandheteroge- neous user preference, model the head selection and airtime al- location usinggeneralizedNBS, andthen discusstheexistence of optimalsolutionforbothcases.Theintentionofusinggeneralized NBS insteadof standardNBS is tosee whetherbargainingpower allows the head to be selected to gain higher utility than other users,whichmotivatestheuserstobecometheheadwillingly.

3.2. Homogeneoususerpreference

Assume thenodes havehomogeneous preferenceon thedata, i.e., they are interestedin any data that any other nodes would liketodisseminate.Defineadisseminationofthedataofanynodei thesetoftransmissions(orlinks)thatsendi’sdatafromonenode totheother.Fora peripheralnode,itsdisseminationincludesthe transmissionfromitselftotheheadandN−2transmissionsfrom theheadtoothernodesinthegroup.Forthehead,itsdissemina- tionconsistsofN−1transmissionsfromitselftoalltheperipheral nodes.Denotex_itheairtimeforthedisseminationofnodei’sdata, thentheairtimeconstraintisgivenby

N

i=1

xi≤T (4)

whereTistheavailableairtime.Foreachnodei,wehave

0≤x_i≤ (^k,j)∈Li

z_i

c_{k j} (5)

wherez_iisthesizeofallthedatainMiandLiisthesetofallthe linksthat disseminatei’sdata.Theconstraintshownin(5)means that the airtime allocated to i’s dissemination should not exceed whatitneeds.

Withinthedisseminationofanynode’sdata,wealsoaimafair datadistributionamongallthetransmissions.Ideally,theprogress of all the transmissions of a given dissemination, definedas the amountofdatatransmitted,shouldbeequalwhenthedissemina- tionstops.Mathematically,wehave

θ

i=ck jxⁱ_{k j},

∀ (

k,j

)

∈Li (6) where

θ

idenotestheamountofdatatransmittedbyeverylinkin Liandxⁱ_{k j}istheairtimeforlink(k,j)inLitodisseminatenodei’s data.Nowwecanexpresstheairtimeforsendingi’sdataviaeach linkinLiintermsof

θ

i:

xⁱ_{k j}=

θ

ⁱ

c_{k j},

∀ (

k,j

)

∈Li. (7)

Bydefinition,theairtimeforthedisseminationofnode i’sdatais thesummationoftheairtimeforallthelinksinLi:

x_i= (^k,j)∈Li

xⁱ_{k j}= (^k,j)∈Li

θ

i

c_{k j}. (8)

DoingabasictransformationofEq.(8),weget

θ

i= xi

(k,j)∈Li 1 c_{k j}

. (9)

Naturally,theamountofdataidisseminateswithinTcanbegiven by

d_i=N_i

θ

i= Nixi

(k,j)∈Li 1 ck j

(10) whereN_iisthenumberoftransmissionsinthedisseminationofi’s datainT.N_i=N−1 iftheheadhasnot storedi’sdata,andN_i=

N−2if thehead has.The amount ofdata of interests i receives withinTcanbegivenby

b_i=

h∈G−i

θ

h=

h∈G−i

x_h (k,j)∈Lh

1 ck j

. (11)

where G₋i=G

\ {

ⁱ

}

^{is the set of users in}G except i. If i will be selectedasthehead,theamountofdataiforwardsforothernodes is

fi=

h∈G−i

(

^Nh−

β

h

)

^xh (k,j)∈Lh

1 ck j

(12)

where

β

h=1 means the head has not stored node h’s data and h needs to send the data to the head, otherwise

β

h=0. For a peripheral node i, it only sends its data to the head, therefore s_i= ^βixi

(k,j)∈Li c1k j

. However, for a head i, it not only sends its own databutalsoothers’datatoalltheinterestednodes,thereforewe haves_i=d_i+f_i.Usingaunifiedexpression,wehave

si=ai

_N

ixi

(^k,j)∈Li

1 ck j

+

h∈G−i

(

^Nh−

β

h

)

^xh

(^k,j)∈Lh

1 ck j

+

(

¹−ai

)

β

^ixi

(^k,j)∈Li 1 ck j

.

(13) Inthecaseofhomogeneouspreference,nodesareinterestedinany datathatanyothernodeswouldliketodisseminate.Therefore,we have r_i=b_i, i.e., the amount of data of interests node i receives equals the amount ofdata i receives.Finally, the totalconsumed energyofiis

ei=e^s

(

¹−ai

) β

ix_i

(^k,j)∈Li 1 ck j

+e^r

h∈G−i

x_h

(^k,j)∈Lh 1 ck j

+e^sai

_N

ix_i

(^k,j)∈Li 1 ck j

+

h∈G−i

(

^Nh−

β

h

)

^xh

(^k,j)∈Lh

1 ck j

. (14)

Replacingd_i,b_i,f_i,ande_iin(1)by(10),(11),(12)and(14),we obtaintheutilityofanyuseri:

u_i=

v

_N

ix_i

(^k,j)∈Li 1 ck j

+

h∈G−i

x_h

(^k,j)∈Lh 1 ck j

+ai

γ

h∈G−i

(

^Nh−

β

h

)

^xh (^k,j)∈Lh

1 ck j

−g

e^r

h∈G−i

x_h

(^k,j)∈Lh 1 ck j

+e^s

(

¹−ai

) β

ix_i

(^k,j)∈Li 1 ck j

(15)

+e^sai

N_ix_i

(^k,j)∈Li 1 ck j

+

h∈G−i

(

^Nh−

β

h

)

^xh

(^k,j)∈Lh

1 ck j

From (15), we can see that u_i is a function of x and a where x=(^x1,x₂,...,x_N)^anda=(^a1,a₂,...,a_N)^{.We assumethereisat} leastone(x,a)makesu_i≥0

∀

ⁱ∈G otherwisenodeshavenomoti- vation tojointhegroup anddisseminatetheir data.Formally,the generalizedNBSfortheproblemofheadselectionandairtimeal- location forthecaseofhomogeneous userpreferencecan be ob- tainedbymaximizingthefollowinggeneralizedNashproduct:

maxx,a

N i=1

u_i

(

^x,a

)

^{αi (16)}

s.t.

N

i=1

xi≤T (17)

0≤xi≤ (^k,j)∈Li

z_i

c_{k j},

∀

^{i∈G (18)}

u_i

(

^x,a

)

^≥0,

∀

^{i∈G (19)}

ei≤Ei,

∀

ⁱ∈G (20)

ai=

{

^1,0

}

^,

∀

^{i∈G (21)}

N

i=1

ai=1. (22)

UnderthegeneralizedNBS framework, ahighergeneralizedNash product means a better decision of head selection and airtime allocation. In our case, users’ utilities are zero at the disagree- ment point since they will get nothing if no group is formed.

Eq.(17)representstheairtime constraintforall the groupmem- bers.Eq.(18)statesthattheairtimeallocatedtothedissemination ofanyuser’sdata shouldbe nonnegativeandnot be longer than themaximum airtime required.Eq.(19) ensures individual ratio- nality.Eq.(20)limitsthe energyconsumption ofeach usertoits energybudget.Finally,Eq.(21)and(22)indicatethatonly oneof theuserswouldbeselectedasthegrouphead.

Theproblem(16) hasatleastone optimalsolution. Theproof ofthisstatementisskipped,becauseinSection3.3below,amore generalcase,theheterogeneouscase,isstudied.Forthismoregen- eralcase, it will be proved withdetails that the samestatement holds,asshowninTheorem1, forthemoregeneralizedproblem (32)thatcorrespondstotheproblem(16)here.

3.3.Extensiontoheterogeneoususerpreference

Theabove modelapplies toMSN systems whereusersare in- terestedin the same data. However, in some MSN systems (e.g., publish-subscribe systems), users may be interested in different data.Inthissection,weextendtheabovemodeltocaseswithhet- erogeneoususerpreferences.

Consider that there could be multipledata in Mi. Let L^m_i be theset of linksthat disseminate node i’s data m. Denote x^m_i the airtimefordisseminatingi’sdata m.Then the totalairtime x_ifor disseminatingi’sdataisM_i

m=1x^m_i whereM_i=

|

Mi

|

^isthenumber

ofdatainMi.Thentheairtimeconstraintisgivenby N

i=1 Mi

m=1

x^m_i ≤T. (23)

Foreachnodeianditsdatam,wehave

0≤x^m_i ≤ (^k,j)∈L^mi

z^m_i

c_{k j} (24)

wherez^m_i isthesizeofdatam.Thetotalamountofdataidissem- inatesis

d_i=

Mi

m=1

N_i^m x^m_i (k,j)∈L^mi

1 ck j

(25)

whereN^m_i isthenumberoftransmissionsinthedisseminationof i’sdatam.DenoteBithesetofnodesthatdisseminatedatatoi(or equivalentlythesetofnodesthatiisinterestedintheirdata).The amountofdataofinterestsireceivesis

b_i=

h∈Bi

m∈M^hi

x^m_h (k,j)∈L^mh

1 ck j

(26)

whereM^h_i isthesetofh’sdatasenttoi.Ifiwillbetheheadafter selection,theamountofdataitforwardsis

fi=

h∈G−i Mh

m=1

(

^Nmh −

β

h^m

)

^xmh (k,j)∈L^mh

1 ck j

(27)

where

β

_h^m=1 means the head has not stored h’s data m and h needs to send m to the head,otherwise

β

h^m=0. The amount of dataisendsisgivenby

si=ai

^Mi

m=1

N_i^m x^m_i

(^k,j)∈L^mi 1 ck j

+

h∈G−i Mh

m=1

(

^Nh^m−

β

h^m

)

^xmh (^k,j)∈L^mh

1 ck j

(28) +

(

¹−ai

)

Mi

m=1

x^m_i

β

i^m

(k,j)∈L^mi 1 ck j

.

Foraperipheralnodei,westillhaver_i=b_i.However,forthehead, itdoesnothold,sinceitmayreceivesomedataofnointerestand onlyforforwarding.Thentheamountofdataireceivesis

r_i=a_i

h∈G−i Mh

m=1

x^m_h

β

h^m

(k,j)∈L^mh 1 ck j

+

(

¹−a_i

)

h∈Bi

m∈M^hi

x^m_h (k,j)∈L^mh

1 ck j

. (29) Finally,thetotalconsumedenergyofiis

e_i=

(

¹−a_i

)

e^s

Mi

m=1

x^m_i

β

i^m

(k,j)∈L^mi 1 ck j

+e^r

h∈Bi

m∈M^hi

x^m_h (k,j)∈L^mh

1 ck j

+ai e^s

^Mi

m=1

N_i^m x^m_i (k,j)∈L^mi

1 ck j

+

h∈G−i Mh

m=1

(

^Nh^m−

β

h^m

)

x^m_h

(k,j)∈L^mh 1 ck j

+e^r

h∈G−i Mh

m=1

x^m_h

β

h^m

(k,j)∈L^mh 1 ck j

. (30)

Replacing d_i,b_i, f_i, ande_i in (1)by (25), (26), (27), and(30), we obtaintheutilityofanyuseri:

ui=

v

^Mi

m=1

N_i^mx^m_i (k,j)∈L^mi

1 ck j

+

h∈Bi

m∈M^hi

x^m_h (k,j)∈L^mh

1 ck j

+ai

γ

h∈G−i Mh

m=1

(

^Nh^m−

β

h^m

)

^xmh (k,j)∈L^mh

1 ck j

−g

(

¹−ai

)

e^s

Mi

m=1

x^m_i

β

i^m

(k,j)∈L^mi 1 ck j

+e^r

h∈Bi

m∈M^hi

x^m_h (k,j)∈L^mh

1 ck j

+a_i

e^s

^Mi

m=1

N_i^m x^m_i (k,j)∈L^mi

1 ck j

(31)

+

h∈G−i Mh

m=1

(

^Nmh −

β

h^m

)

^xmh (k,j)∈L^mh

1 ck j

+e^r

h∈G−i Mh

m=1

x^m_h

β

h^m

(k,j)∈L^mh 1 ck j

Formally, the generalized NBS for the problem ofhead selec- tionandairtimeallocationforthecaseofheterogeneoususerpref- erencecanbeobtainedbymaximizing thefollowingoptimization problem:

maxx,a

N i=1

ui

(

^x,a

)

^{αi (32)}

s.t.

N

i=1 Mi

m=1

x^m_i ≤T (33)

0≤x^m_i ≤ (k,j)∈L^mi

z^m_i

ck j,

∀

ⁱ∈G,m∈Mi (34)

u_i

(

^x,a

)

^≥0,

∀

^{i∈G (35)}

e_i≤E_i,

∀

^{i∈G (36)}

ai=

{

^1,0

}

^,

∀

^{i∈G (37)}

N

i=1

a_i=1. (38)

Constraints (33)–(38) have the same meaning with constraints (17)–(22),respectively.Assumingthereisatleastone(x,a)makes u_i≥0

∀

ⁱ∈G,wehavethefollowingtheorem.

Theorem1. Thereexistsatleastoneoptimalsolutiontooptimization problem(32)–(38)forjointheadselectionandairtimeallocation.

Proof. Infact, theoptimizationproblem(32)–(38)hastwo levels ofoptimization.Atthelowerlevel,eachuseriinthegroupsolves asub-problem(alocalgeneralizedNBSproblem)thatfindsoptimal airtimeallocationamongall theuserswhenuseriisthehead.At thehigherlevel,wehaveamasterproblemthatchoosesthebesti tobethehead,whichgivesthehighestgeneralizedNashproduct.

Mathematically,thesub-problemforeachuserisgivenby maxx

N i=1

u_i

(

^x

)

^αi

s.t.

N

i=1 Mi

m=1

x^m_i ≤T

0≤x^m_i ≤ (k,j)∈L^mi

z^m_i

ck j,

∀

ⁱ∈G,m∈Mi (39)

ui

(

^x

)

≥0,

∀

^i∈G

e_i≤E_i,

∀

^i∈G.

whereaisfixedandu_iisonlyafunctionofx.Sincev(·)and−g(·) arestrictlyconcavefunctions,bytheconcavitypreservingrulesin [26],wecanseethatu_iisastrictlyconcavefunctioninx.Sincethe functionoflogisconcaveandmonotonic,theobjectivefunctionof problem(39)isequivalentto[18]

maxx

N

i=1

α

ilogui

(

^x

)

⁽⁴⁰⁾

It is easy to see that (40) is strictly concave andthe constraints in (39) are convex. Additionally, we have assumed that there is at least one feasible point, meaning the constraint set is non- empty,thereforethereexistsauniqueoptimalsolutiontoproblem (40)and equivalently to problem(39)[26].

Atthehigherlevel,themasterproblemis maxa p

(

^a

)

s.t. a_i=

{

¹,0

}

,

∀

ⁱ∈G (41)

N

i=1

a_i=1

where p(^a)=max

x

N

i=1u_i(^x)^{αi is the optimal objective value of} problem(39)foragivena(namely, agivenuserbeingthehead).

Sincetherewillbeonlyonea_iequals1andtherestare0,theob- jectiveofthemasterproblem(41)isessentiallyfindingthelargest within Nrealnumbers,whichalways exists.Thepair(s) (x,a)re- sulting inthe largest number willbe theoptimal solution(s)⁴ to thewholeproblem.

4Strictly speaking, there might be multiple maximum in N real numbers. There- fore, we do not claim uniqueness of the optimal solution.