Vehicular content distribution

• US 8,542,636 B2
• Filed: 01/03/2011
• Issued: 09/24/2013
• Est. Priority Date: 01/04/2010
• Status: Expired due to Fees

• Current Assignee: Lili Qiu, Yin Zhang
• Original Assignee: Lili Qiu, Yin Zhang
• Inventors: Qiu, Lili, Zhang, Yin
• Primary Examiner(s): Llu, Jung-Jen
• Application Number:
  US12/983,884
• Publication Number:
  US 20110164562A1
• Time in Patent Office: 995 Days
• Field of Search: 370/203, 370204-215, 370229-240, 370310-337, 370338-350, 370351-394, 370/395.1, 370/395.3, 370/395.4, 370/395.41, 370/395.42, 370/395.5, 370/395.52, 370/395.53, 370412-421, 370431-457, 370458-463, 370464-497, 370498-522, 370523-520, 370521-529
• US Class Current: 370/328
• CPC Class Codes: H04W 48/04 based on user or terminal location or mobility data, e.g. moving direction, speed
• CPC Class Codes: H04W 72/52 based on load
• CPC Class Codes: H04W 72/543 based on requested quality, e.g. QoS

Abstract

A system and method provides an electronic content to a vehicle from access point(s) within a network using a controller. The controller divides the electronic content into one or more files wherein each file contains at least one packet, and generates two or more random linear combinations of the packets within each file. For each file, each random linear combination of the packets is replicated to a different access point within the network. The electronic content is provided to the vehicle using at least one of the different access points. The controller can also determine a set of nearest trajectories for the vehicle in a location database that match a recent location history for the vehicle. For each determined nearest trajectory, one or more mobility trajectories are determined for the vehicle, and a set of access points are determined that correspond to the determined mobility trajectories for the vehicle.

Claims

1. A method of providing an electronic content to a vehicle from one or more access points within a network using a controller, the method comprising the steps of:

dividing the electronic content into one or more files wherein each file contains at least one packet using the controller;

generating two or more random linear combinations of the packets within each file using the controller;

for each file, replicating each random linear combination of the packets to a different access point within the network in accordance with a linear program; and

providing the electronic content to the vehicle using at least one of the different access points by associating the vehicle with one of the different access points, providing a list of the files received and a list of the files requested from the vehicle to the associated access point, and downloading the files within the list of the files requested that are available at the associated access point to the vehicle until the download is complete or the vehicle is no longer associated.

2. The method as recited in claim 1, wherein:

the vehicle comprises a scooter, a motorcycle, a car, a truck, a boat, or a non-motorized vehicle; and

at least one of the access points is communicably coupled to the Internet.

3. The method as recited in claim 1, wherein the electronic content is provided to an electronic device within the vehicle comprising a computer, a communications device, a smartphone, a personal data assistant, an entertainment device, an information center or a combination thereof.

4. The method as recited in claim 1, wherein the linear program comprises the following equations:

Input;

Intv, WCap(a), InCap(a), OutCap(i), CT(a,v), AP(v), size(f), has(n,f), Q(v,f), γ

Output;

x(f,i,a) and D(v,f,a)

Maximize;

Σ

_vΣ

_fΣ

<sub>aε

AP(v)</sub>Q(v,f)D(v,f,a)−

γ

Σ

<sub>iε

I</sub>Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)

Subject to;

Σ

_fD(v,f,a)≦

WCap(a)×

CT(a,v)∀

v,aε

AP(v)  

 

[C1]

Σ

<sub>aε

AP(v)</sub>D(v,f,a)≦

size(f)−

has(v,f)∀

v,f  

 

[C2]

D(v,f,a)≦

has(a,f)+Σ

<sub>iε

I</sub>x(f,i,a)∀

v,f,aε

AP(v)  

 

[C3]

Σ

<sub>iε

I</sub>x(f,i,a)≦

size(f)−

has(a,f)∀

f,aε

A  

 

[C4]

Σ

<sub>iε

I</sub>Σ

_fx(f,i,a)≦

InCap(a)×

Intv∀

aε

A  

 

[C5]

Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)≦

OutCap(i)×

Intv∀

iε

I  

 

[C6]

where v is a vehicle, f is a file, a is an AP, i is a node with wireline connectivity (which may or may not be an AP, e.g., a Web server), Intv is an interval duration, A is the set of all the APs, I is the set of all the nodes with wireline connectivity, AP(v) is the set of APs that vehicle v will visit, , γ

is a weighting factor, Q(v,f) is the probability that v is interested in file f, D(v,f,a) is the amount of traffic in file f vehicle v should download from AP a during a contact in the next interval, x(f, n1, n2) is the amount of traffic in file f to replicate from node n1 to node n2 during the current interval, CT(a,v) is average contact time of vehicle v at AP a, WCap(a) is wireless capacity at AP a, InCap(a) is incoming wireline access link capacity at AP a, OutCap(i) is outgoing wireline access link capacity at node i, has(n,f) is amount of file f a node n has (the node n can be either an AP a or vehicle v), and size(f) is the size of file f.

5. The method as recited in claim 1, wherein the different access points are determined based on a mobility prediction algorithm.

6. The method as recited in claim 1, further comprising the step of using the vehicle to transfer one or more files from a first access point to a second access point.

7. The method as recited in claim 6, wherein the linear program comprises the following equations:

Input;

Intv, WCap(a), InCap(a), OutCap(i), CT(a,v), AP(v), size(f), has(n,f), Q(v,f), γ

, y(f,a₁, a₂), N_path, RelayF

Output;

x(f,i,a) and D(v,f,a)

Maximize;

Σ

_vΣ

_fΣ

<sub>aε

AP(v)</sub>Q(v,f)D(v,f,a)−

γ

Σ

<sub>iε

I</sub>Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)

Subject to;

Σ

_fmax_a2y(f,a₁,a₂)+Σ

_fΣ

_a2y(f,a_2, a₁)≦

WCap(a1)×

CT(a1)×

RelayF∀

a₁  

 

[C0]

Σ

_fD(v,f,a)≦

WCap(a)×

CT(a,v)×

(1−

RelayF)∀

v,aε

AP(v)  

 

[C1]

Σ

<sub>aε

AP(v)</sub>D(v,f,a)≦

size(f)−

has(v,f)∀

v,f  

 

[C2]

D(v,f,a)≦

has(a,f)+)+Σ

<sub>iε

I</sub>x(f,i,a)+Σ

<sub>a2≠

a</sub>y(f,a₂,a)×

N_path∀

v,f,aε

AP(v)  

 

[C3]

Σ

<sub>iε

I</sub>x(f,i,a)≦

size(f)−

has(a,f)∀

f,aε

A  

 

[C4]

Σ

<sub>iε

I</sub>Σ

_fx(f,i,a)≦

InCap(a)×

Intv∀

aε

A  

 

[C5]

Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)≦

OutCap(i)×

Intv∀

iε

I  

 

[C6]

where v is a vehicle, f is a file, a is an AP, i is a node with wireline connectivity (which may or may not be an AP, e.g., a Web server), Intv is an interval duration, A is the set of all the APs, I is the set of all the nodes with wireline connectivity (including the web or content server), γ

is a weighting factor, AP(v) is the set of APs that vehicle v will visit, Q(v, f) is the probability that v is interested in file f, D(v, f, a) is the amount of traffic in file f vehicle v should download from AP a during a contact in the next interval, x(f, n1, n2) is the amount of traffic in file f to replicate from node n1 to node n2 during the current interval CT(a, v) is average contact time of vehicle v at AP a, WCap(a) is wireless capacity at AP a, InCap(a) is incoming wireless access link capacity at AP a, OutCap(i) is outgoing wireline access link capacity at node i, has(n, f) is amount of file f a node n has, size(f) is the size of file f, y(f, a₁, a₂) denotes the amount of traffic to be relayed via wireless from AP a₁ to AP a₂ for a given file f in the current interval, RelayF is the fraction of capacity reserved for relaying, and N_path is the number of paths.

8. The method as recited in claim 1, wherein the network comprises a mesh network.

9. The method as recited in claim 8, wherein the linear program comprises the following equations:

Input;

Intv, WCap(a), InCap(a), OutCap(i), CT(a, v), AP(v), size(f), has(n,f), Q(v,f), γ

,γ

′

, MCap(a′

,a), z(f,a′

,a), ETX(a′

,a)

Output;

x(f,i,a) and D(v,f,a)

Maximize;

Σ

_vΣ

_fΣ

<sub>aε

AP(v)</sub>Q(v,f)D(v,f,a)−

γ

Σ

<sub>iε

I</sub>Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)−

γ

′

Σ

_fΣ

<sub>(a ′

,a)ε

mesh</sub>z(f,a′

,a)

Subject to;

Σ

_fD(v,f,a)≦

WCap(a)×

CT(a,v)∀

v,aε

AP(v)  

 

[C1]

Σ

<sub>aε

AP(v)</sub>D(v,f,a)≦

size(f)−

has(v,f)∀

v,f  

 

[C2]

D(v,f,a)≦

has(a,f)+Σ

<sub>iε

I</sub>x(f,i,a)+Σ

<sub>(a′

,a)ε

mesh</sub>z(f,a′

,a)∀

v,f,aε

AP(v)  

 

[C3]

Σ

<sub>iε

I</sub>x(f,i,a)≦

size(f)−

has(a,f)∀

f,aε

A  

 

[C4]

Σ

<sub>iε

I</sub>Σ

_fx(f,i,a)≦

InCap(a)×

Intv∀

aε

A  

 

[C5]

Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)≦

OutCap(i)×

Intv∀

iε

I  

 

[C6]

z(f,a′

,a)≦

has(a′

,f)  

 

[C7]

Σ

<sub>f,(a′

,a)ε

mesh</sub>ETX(a′

,a)z(f,a′

,a)MCap(a′

,a)≦

1 

 

[C8]

where v is a vehicle, f is a file, a is an AP, i is a node with wireline connectivity (which may or may not be an AP, e.g., a Web server), Intv is an interval duration, A is the set of all the APs, I is the set of all the nodes with wireline connectivity, AP(v) is the set of APs that vehicle v will visit, Q(v,f) is the probability that v is interested in file f, D(v, f , a) is the amount of traffic in file f vehicle v should download from AP a during a contact in the next interval, x(f, n1, n2) is the amount of traffic in file f to replicate from node n1 to node n2 during the current interval, CT (a, v) is average contact time of vehicle v at AP a, WCap(a) is wireless capacity at AP a, InCap(a) is incoming wireline access link capacity at AP a, OutCap(i) is outgoing wireline access link capacity at node i, has(n,f) is amount of file f a node n has, size(f) is the size of file f, γ and

γ

′

are weighting factors, MCap(a′

, a) denotes the capacity of a wireless link from AP a′

to a in the mesh network, z(f, a′

, a) denotes the amount of content to replicate from AP a′

to a for file f through the mesh network, and ETX(a′

, a) denotes the average number of transmissions required to send a packet from a′

to a through the mesh.

10. The method as recited in claim 1, further comprising the step of uploading files from the vehicle to one of the access points as part of the replication process.

11. The method as recited in claim 10, further comprising the step of uploading one or more files between the vehicle and the associated access point while the vehicle is downloading the files within the list of the files.

12. The method as recited in claim 1, further comprising the step of replicating the files using inter-flow network coding.

25. The method as recited in claim 11, further comprising the step of ordering the files to upload based on a future demand for the files at the associated access point wherein the future demand is estimated using the formula Σ

{v;

v visits AP} Q(v,f) demand(v,f), where Q(v,f) is the probability that v is interested in file f and demand(v,f) is the expected size of file f vehicle v is interested in.

13. A system comprising:

at least one vehicle;

one or more access points within a network;

a controller communicably coupled to the one or more access points, wherein the controller is configured to;

(i) divide the electronic content into one or more files wherein each file contains at least one packet, (ii) generate two or more random linear combinations of the packets within each file, and (iii) for each file, replicate each random linear combination of the packets to a different access point within the network in accordance with a linear program; and

wherein at least one of the different access points provide the electronic content to the vehicle by associating the vehicle with one of the different access points, providing a list of the files received and a list of the files requested from the vehicle to the associated access point, and downloading the files within the list of the files requested that are available at the associated access point to the vehicle until the download is complete or the vehicle is no longer associated.

14. The system as recited in claim 13, wherein the vehicle comprises a scooter, a motorcycle, a car, a truck, a boat, or a non-motorized vehicle.

15. The system as recited in claim 13, wherein:

the electronic content is provided to an electronic device within the vehicle comprising a computer, a communications device, a smartphone, a personal data assistant, an entertainment device, an information center or a combination thereof; and

at least one of the access points is communicably coupled to the Internet.

16. The system as recited in claim 13, wherein the linear program comprises following equations:

Input;

Intv, WCap(a), InCap(a), OutCap(i), CT(a,v), AP(v), size(f), has(n,f), Q(v,f), γ

Output;

x(f,i,a) and D(v,f,a)

Maximize;

Σ

_vΣ

_fΣ

<sub>aε

AP(v)</sub>Q(v,f)D(v,f,a)−

γ

Σ

<sub>iε

I</sub>Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)

Subject to;

Σ

_fD(v,f,a)≦

WCap(a)×

CT(a,v)∀

v,aε

AP(v)  

 

[C1]

Σ

<sub>aε

AP(v)</sub>D(v,f,a)≦

size(f)−

has(v,f)∀

v,f  

 

[C2]

D(v,f,a)≦

has(a,f)+Σ

<sub>iε

I</sub>x(f,i,a)∀

v,f,aε

AP(v)  

 

[C3]

Σ

<sub>iε

I</sub>x(f,i,a)≦

size(f)−

has(a,f)∀

f,aε

A  

 

[C4]

Σ

<sub>iε

I</sub>Σ

_fx(f,i,a)≦

InCap(a)×

Intv∀

aε

A  

 

[C5]

Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)≦

OutCap(i)×

Intv∀

iε

I  

 

[C6]

where v is a vehicle, f is a file, a is an AP, i is a node with wireline connectivity (which may or may not be an AP, e.g., a Web server), Intv is an interval duration, A is the set of all the APs, I is the set of all the nodes with wireline connectivity, AP(v) is the set of APs that vehicle v will visit, γ

is a weighting factor, Q(v, f) is the probability that v is interested in file f, D(v, f, a) is the amount of traffic in file f vehicle v should download from AP a during a contact in the next interval, x(f, n1, n2) is the amount of traffic in file f to replicate from node n1 to node n2 during the current interval, CT(a, v) is average contact time of vehicle v at AP a, WCap(a) is wireless capacity at AP a, InCap(a) is incoming wireline access link capacity at AP a, OutCap(i) is outgoing wireline access link capacity at node i, has(n,f) is amount of file f a node n has (the node n can be either an AP a or vehicle v), and size(f) is the size of file f.

17. The system as recited in claim 13, wherein the different access points are determined based on a mobility prediction algorithm.

18. The system as recited in claim 13, wherein the vehicle transfers one or more files from a first access point to a second access point.

19. The system as recited in claim 18, wherein the linear program comprises the following equations:

Input;

Intv, WCap(a), InCap(a), OutCap(i), CT(a,v), AP(v), size(f), has(n,f), Q(v,f), γ

, y(f,a₁,a₂), N_path, RelayF

Output;

x(f,i,a) and D(v,f,a)

Maximize;

Σ

_vΣ

_fΣ

<sub>aε

AP(v)</sub>Q(v,f)D(v,f,a)−

γ

Σ

<sub>iε

I</sub>Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)

Subject to;

Σ

_fmax_a2y(f,a₁,a₂)+Σ

_fΣ

_a2y(f,a₂, a₁)≦

WCap(a1)×

CT(a1)×

RelayF∀

a₁  

 

[C0]

Σ

_fD(v,f,a)≦

WCap(a)×

CT(a,v)×

(1−

RelayF)∀

v,aε

AP(v)  

 

[C1]

Σ

<sub>aε

AP(v)</sub>D(v,f,a)≦

size(f)−

has(v,f)∀

v,f  

 

[C2]

D(v,f,a)≦

has(a,f)+)+Σ

<sub>iε

I</sub>x(f,i,a)+Σ

<sub>a2≠

a</sub>y(f,a₂,a)×

N_path ∀

v,f,aε

AP(v)  

 

[C3]

Σ

<sub>iε

I</sub>x(f,i,a)≦

size(f)−

has(a,f)∀

f,aε

A  

 

[C4]

Σ

<sub>iε

I</sub>Σ

_fx(f,i,a)≦

InCap(a)×

Intv∀

aε

A  

 

[C5]

Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)≦

OutCap(i)×

Intv∀

aε

I  

 

[C6]

where v is a vehicle, f is a file, a is an AP, i is a node with wireline connectivity (which may or may not be an AP, e.g., a Web server), Intv is an interval duration, A is the set of all the APs, I is the set of all the nodes with wireline connectivity (including the web or content server), γ

is a weighting factor, AP(v) is the set of APs that vehicle v will visit, Q(v,f) is the probability that v is interested in file f, D(v, f, a) is the amount of traffic in file f vehicle v should download from AP a during a contact in the next interval, x(f, nl, n2) is the amount of traffic in file f to replicate from node n1 to node n2 during the current interval, CT(a, v) is average contact time of vehicle v at AP a, WCap(a) is wireless capacity at AP a, InCap(a) is incoming wireline access link capacity at AP a, OutCap(i) is outgoing wireline access link capacity at node i, has(n,f) is amount of file f a node n has, size(f) is the size of file f, y(f, a₁, a₂) denotes the amount of traffic to be relayed via wireless from AP a₁ to AP a₂ for a given file f in the current interval, RelayF is the fraction of capacity reserved for relaying, and N_path is the number of paths.

20. The system as recited in claim 13, wherein the network comprises a mesh network.

21. The system as recited in claim 20, wherein the linear program comprises the following equations:

Input;

Intv, WCap(a), InCap(a), OutCap(i), CT(a,v), AP(v), size(f), has(n,f), Q(v,f), γ

, γ

′

, MCap(a′

, a), z(f,a′

,a), ETX(a′

, a)

Output;

x(f,i,a) and D(v,f,a)

Maximize;

Σ

_vΣ

_fΣ

<sub>aε

AP(v)</sub>Q(v,f)D(v,f,a)−

γ

Σ

<sub>iε

I</sub>Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)−

γ

′

Σ

_fΣ

<sub>(a′

,a)ε

mesh</sub>z(f,a′

,a)

Subject to;

Σ

_fD(v,f,a)≦

WCap(a)×

CT(a,v)∀

v,aε

AP(v)  

 

[C1]

Σ

<sub>aε

AP(v)</sub>D(v,f,a)≦

size(f)−

has(v,f)∀

v,f  

 

[C2]

D(v,f,a)≦

has(a,f)+Σ

<sub>iε

I</sub>x(f,i,a)+Σ

<sub>a′

,a)ε

mesh</sub>z(f, a′

,a)∀

v,f,aε

AP(v)  

 

[C3]

Σ

<sub>iε

I</sub>x(f,i,a)≦

size(f)−

has(a,f)∀

f,aε

A  

 

[C4]

Σ

<sub>iε

I</sub>Σ

_fx(f,i,a)≦

InCap(a)×

Intv∀

aε

A  

 

[C5]

Σ

<sub>aε

A</sub>Σ

_fx(f,i,a)≦

OutCap(i)×

Intv∀

iε

I  

 

[C6]

z(f,a′

,a)≦

has(a′

,f)  

 

[C7]

Σ

<sub>f,(a′

,a)ε

mesh</sub>ETX(a′

,a)z(f,a′

,a)MCap(a′

,a)≦

1  

 

[C8]

where v is a vehicle, f is a file, a is an AP, i is a node with wireline connectivity (which may or may not be an AP, e.g., a Web server), Intv is an interval duration, A is the set of all the APs, I is the set of all the nodes with wireline connectivity, AP(v) is the set of APs that vehicle v will visit, Q(v, f) is the probability that v is interested in file f, D(v, f, a) is the amount of traffic in file f vehicle v should download from AP a during a contact in the next interval, x(f, n1, n2) is the amount of traffic in file f to replicate from node n1 to node n2 during the current interval, CT (a, v) is average contact time of vehicle v at AP a, WCap(a) is wireless capacity at AP a, InCap(a) is incoming wireline access link capacity at AP a, OutCap(i) is outgoing wireline access link capacity at node i, has(n, f) is amount of file f a node n has, size(f) is the size of file f, γ and

γ

′

are weighting factors, MCap(a′

, a) denotes the capacity of a wireless link from AP a′

to a in the mesh network, z(f, a′

, a) denotes the amount of content to replicate from AP a′

to a for file f through the mesh network, and ETX(a′

, a) denotes the average number of transmissions required to send a packet from a′

to a through the mesh.

22. The system as recited in claim 13, wherein files are uploaded from the vehicle to one of the access points as part of the replication process.

23. The system as recited in claim 22, further comprising the step of uploading one or more files between the vehicle and the associated access point while the vehicle is downloading the files within the list of the files.

24. The system as recited in claim 13, wherein the files are further replicated using inter-flow network coding.

26. The method as recited in claim 23, further comprising the step of ordering the files to upload based on a future demand for the files at the associated access point wherein the future demand is estimated using the formula Σ

{v;

v visits AP} Q(v,f) demand(v,f), where Q(v,f) is the probability that v is interested in file f and demand(v,f) is the expected size of file f vehicle v is interested in.