Tối ưu cơ hội truyền gói tin trong mạng vô tuyến sử dụng lý thuyết trò chơi
TỐI ƯU CƠ HỘI TRUYỀN GÓI TIN TRONG MẠNG VÔ TUYẾN SỬ
DỤNG LÝ THUYẾT TRÒ CHƠI
MAXIMIZING PACKET TRANSMISSION OPPORTUNITIES IN THE
WIRELESS NETWORK BY USING THE GAME THEORY
Nguyễn Chánh Tín 1, Phan Văn Ca 2
1 2 Trường đại học Sư phạm Kỹ thuật TP.HCM
TÓM TẮT
Trong bài báo này, tác giả phát triển mô hình truyền gói tin cơ hội dựa trên lý thuyết trò chơi
cho mạng vô tuyến hoạt động trong điều kiện nguồn năng lượng thấp. Để giảm thiểu việc truyền
gói tin không thành công do lỗi kênh truyền và xung đột trong quá trình truyền gói tin gây ra sự
lãng phí năng lượng, chiến lược truyền gói tin cơ hội cố gắng truyền gói tin ở điều kiện kênh
truyền tốt nhất với ràng buộc về độ trễ gói tin với mô hình kênh truyền fading biến thiên theo thời
gian. Mô hình lý thuyết trò chơi ngẫu nhiên kết hợp chi phí được đề xuất để xác định một ngưỡng
tối ưu cho việc truyền gói tin theo cơ chế truyền thông cơ hội. Kết quả mô phỏng cho thấy với
chiến lược truyền thông cơ hội, các nút mạng có xu hướng trì hoãn truyền trong điều kiện kênh
truyền xấu nhằm tránh xung đột và giảm tỷ lệ mất gói tin dẫn đến việc tăng hiệu quả sử dụng năng
lượng của mỗi nút và kéo dài thời gian hoạt động của mạng.
Từ khóa: Lý thuyết trò chơi; chiến lược truyền thông cơ hội; mạng vô tuyến; kênh truyền biến
thiên theo thời gian; trò chơi ngẫu nhiên kết hợp hàm chi phí.
ABSTRACT
In this paper, the authors have developed a game theory framework for opportunity
communication strategy for wireless networks that operating in a strict energy-constrained
environment. In order to minimize unsuccessful transmission due to channel errors and packet
collisions that causing a waste of energy, the opportunity communication strategy attempts to
transmit at good channel conditions while meeting the delay constraint under time-varying
wireless channel. Thus a constrained cost-coupled stochastic game algorithm is formulated to
obtain an optimal threshold for successful transmission in the opportunistic transmission manner.
The simulation result shows that with the opportunity transmission strategy, the nodes trend to
defer their transmissions in bad channel conditions to avoid collision and reduce packet loss rate.
This can lead to improve the performance of energy usage at each node as well as to prolong the
network lifetime.
Keywords: Game theory; opportunistic transmission; wireless network; time-varying wireless
channel; cost-coupled stochastic.
kế đề xuất cho hiệu năng về tổng thông lượng
đạt được ở cân bằng Nash duy nhất và độ cân
bằng tải truyền giữa các nút mạng so với thuật
toán DCF chuẩn. Trong bài báo số [2], các tác
giả đề xuất một phương pháp tiếp cận mới dựa
trên lý thuyết trò chơi để thay đổi tốc độ, điều
chế và công suất trong thuật toán trò chơi. Tất
cả người dùng đều hài lòng với việc kết hợp các
quy tắc trò chơi. Tính ích kỷ của người sử dụng
độc lập bị hạn chế trong khuôn khổ này. Tính
ích kỷ trò chơi đạt đến điểm mong muốn được
gọi là điểm cân bằng Nash. Thông qua các kết
quả khác nhau, tác giả thấy rằng tất cả người
dùng đều có một sự cân bằng giữa tối đa hóa lợi
1. GIỚI THIỆU
Trong những năm gần đây, lý thuyết trò
chơi đã trở thành một công cụ thiết yếu, hiệu
quả để phân tích và thiết kế mạng vô tuyến.
Giao thức đa truy cập cảm nhận sóng mang
(CSMA) ứng dụng lý thuyết trò chơi cho mạng
vô tuyến đang được xem như là một giải pháp
thay thế CSMA cổ điển dựa trên cơ chế back-
off ngẫu nhiên [1]. Trong bài báo này, các tác
giả đưa ra một thiết kế giao thức MAC dựa trên
lý thuyết trò chơi cho mạng vô tuyến và thực
hiện thử nghiệm trên mạng vô tuyến trong nhà
với 22 nút lập trình được dựa trên chuẩn IEEE
802.11. Các phép đo của tác giả cho thấy thiết
ích và tối thiểu năng lượng truyền, giữa tốc độ
và kiểu điều chế trong chiến lược của họ. Trong
các mạng vô tuyến đa chặng (multi-hop) [3],
các nút bị hạn chế năng lượng và nguồn tài
nguyên có thể gây ra hiện tượng không sẵn sàng
chuyển tiếp gói tin cho các nút lân cận để tiết
kiệm nguồn năng lượng. Trạng thái này của các
nút có thể làm giảm thông lượng mạng và có
thể làm giảm hiệu suất mạng. Trong các thiết kế
thuật toán lý thuyết trò chơi cho việc chuyển
tiếp lặp lại gói tin, hầu hết các công trình trước
đây đã bỏ qua các yếu tố nhiễu của môi trường
vô tuyến đối với hoạt động của các nút. Thuật
toán trong bài báo này được so sánh với các
thuật toán lý thuyết trò chơi nổi tiếng khác và
kết quả mô phỏng được thực hiện để chứng
minh sự tối ưu của thuật toán ngay cả dưới môi
trường nhiễu.
qua một trò chơi không hợp tác trong đó mỗi
liên kết cố gắng tối đa hoá một hàm lợi ích cục
bộ. Ngoài ra, các tác giả đã chứng minh sự tồn
tại của cân bằng Nash và đã cung cấp các điều
kiện cho tính đơn trị đó và ổn định cho các trò
chơi.
Gần đây bài toán về sự tồn tại của các hành
vi ích kỷ trong kiểm soát truy cập môi trường
mạng vô tuyến cũng đã thu hút sự chú ý của một
số nhà nghiên cứu ( [10], [11], [12], [13]). Các
tác giả [10] đã nghiên cứu hành vi ích kỷ của
các nút trong mạng CSMA/CA bằng cách sử
dụng lý thuyết trò chơi và phát triển một giao
thức cục bộ và phân tán để điều khiển hành vi
ích kỷ các nút cho đến khi cân bằng Nash tối ưu
Pareto. Một bài toán tương tự đã được nghiên
cứu trong [11], trong đó các cuộc tấn công
backoff trong các mạng ad-hoc với các trạm nặc
danh đã được phân tích trong hai mô hình trò
chơi không hợp tác khác nhau: duy nhất và lặp
lại các trò chơi CSMA/CA. Hơn nữa, các tác
giả đã phát triển một chiến lược cho các trạm,
cung cấp một hiệu suất Pareto và sự cân bằng
Nash hoàn hảo của việc tái lập lại trò chơi
CSMA/CA. Trong [12], các tác giả đã nghiên
cứu sự ổn định của CSMA/CA trên nền tảng
mạng vô tuyến với người dùng ích kỷ tham gia
vào trò chơi CSMA/CA không hợp tác. Trong
trò chơi này, giá trị của mỗi người dùng có thể
tự động thay đổi theo tình trạng nghẽn mạng và
tình trạng tiêu thụ năng lượng. Thêm vào đó,
một phương pháp lặp lại có mục đích nhằm đảm
bảo sự hội tụ cân bằng Nash đơn trị. Trong [13],
một trò chơi truy cập ngẫu nhiên cho mạng vô
tuyến đã được trình bày để nghiên cứu hành vi
ích kỷ của nút mạng. Hơn nữa, các tác giả đã
phân tích kỹ thông lượng kênh ở cân bằng Nash
và cung cấp các phân tích tiệm cận của trò chơi
vì số lượng các máy phát ích kỷ đạt đến vô cùng.
Ngoài ra, trò chơi có ràng buộc chi phí ngẫu
nhiên trong đó mỗi người chơi kết hợp với một
chuỗi Markov của riêng mình được kiểm soát
bởi hành động của chính nó đã được nghiên cứu
[14]. Tại mỗi thời điểm, mỗi người chơi sẽ xác
định một hành động theo cho một số chiến lược
nhằm giảm thiểu hàm chi phí trong một số ràng
buộc các chiến lược của nó. Sự tương tác giữa
một số người chơi khác nhau được kết hợp
trong hàm chi phí của họ.
Bên cạnh các phương pháp tiếp cận liên
quan đến chiến lược truyền ở trên, một số cách
tiếp cận khác ( [4], [5], [6], [7], [8]) áp dụng lý
thuyết trò chơi để nghiên cứu kiểm soát tranh
chấp cho mạng vô tuyến. Các tác giả [4] đã
trình bày tổng quan mô hình lý thuyết trò chơi
để nghiên cứu sự tương tác giữa các nút cho các
kênh vô tuyến phổ biến. Ngoài ra, các tác giả
đã nghiên cứu sự cân bằng Nash của trò chơi
này và thiết kế một phương pháp để đạt được
nó theo phương pháp phân phối. Việc mở rộng
bài toán này đã được thảo luận trong bài báo [5].
Trong bài báo này, các tác giả đã khái quát hóa
kiểm soát truy cập trò chơi cho trường hợp mỗi
nút có thể quan sát nhiều tín hiệu tranh chấp để
hướng dẫn chúng cân bằng Nash và đưa ra các
điều kiện cho sự tồn tại duy nhất của sự cân
bằng này. Một khái niệm mới của lý thuyết trò
chơi không hoàn toàn hợp tác đã được đề xuất
( [6], [7], [8]) để cải thiện hiệu suất của
CSMA/CA trong mạng di động ad-hoc. Trong
mô hình trò chơi này, mỗi nút ước lượng trạng
thái trò chơi và thay đổi trạng thái cân bằng
bằng cách thay đổi các tham số tranh chấp để
đạt được hiệu suất tối ưu. Các mở rộng này đã
được trình bày trong bài báo [8]. Trong bài báo
này, các tác giả đã trình bày một phương pháp
ước lượng điều kiện xác suất va chạm dựa trên
kỹ thuật ảo hóa - CSMA và đề xuất một giao
thức lý thuyết trò chơi MAC đơn giản mà có thể
được thực hiện trong các mạng vô tuyến. Một
kỹ thuật đảo ngược của giao thức truy cập ngẫu
nhiên MAC dựa trên backoff sử dụng cách tiếp
cận lý thuyết trò chơi đã được trình bày trong
[9]. Như trình bày trong bài báo, giao thức
backoff hàm mũ là kỹ thuật đảo ngược thông
Mục tiêu của chúng tôi trong bài báo này là
mô hình hóa cơ chế chiến lược truyền thông
(OTS) với điều kiện trễ trong bối cảnh kênh vô
tuyến biến thiên theo thời gian. Trong hệ thống
OTS, trước khi gửi một gói tin, nút gửi đưa ra
quyết định có nên gửi gói tin tại khe thời gian
hiện tại hay trì hoãn việc truyền này dựa trên
trạng thái kênh để giảm thiểu mức tiêu thụ năng
lượng. Các trạng thái của hệ thống OTS được
xây dựng như là trò chơi ngẫu nhiên kết hợp chi
phí dựa trên quá trình Markov để có được chính
sách truyền tải tối ưu.
thông số của mô hình Markov có thể thu được
bằng cách sử dụng các kỹ thuật trong [15].
Hình 1. Mô hình kênh truyền Markov trạng
thái hữu hạn
Phần còn lại của bài báo được bố cục như
sau: phần 2 trình bày mô hình kênh truyền, phần
3 trình bày lý thuyết trò chơi, phần 4 đưa ra kết
quả mô phỏng và đánh giá, phần 5 kết luận của
bài báo.
Đặt fm là tần số Doppler cực đại:
v
fm
(2)
là tốc độ của nút di động và
Trong đó:
v
2. MÔ HÌNH KÊNH TRUYỀN
là bước sóng.
Đề tài xem xét một mạng ad-hoc trong đó
N nút di động sử dụng giao thức MAC phân khe
để truy cập một kênh chung. Trong mạng đó,
trục thời gian được chia thành các khe thời gian
bằng chiều dài Tf và tất cả các nút di động
được đồng bộ với cùng tham chiếu khe thời
gian. Bất cứ khi nào nút di động có một gói tin
đang chờ để gửi đi, nút sẽ thực hiện một trong
hai hành động: Truyền và Hoãn, tương ứng với
truyền gói tin và hoãn truyền gói tin, dựa trên
trạng thái thông tin kênh truyền cục bộ (CSI).
Giả sử CSI được xác định tại mỗi nút ở đầu mỗi
khe thời gian. Ngoài ra, khe thời gian được giả
định đủ ngắn và lưu lượng gói tin đến đủ nhỏ
sao cho gói tin đến mỗi khe thời gian theo phân
Xác suất chuyển tiếp trạng thái được cho
bởi phương trình sau:
yk1
Tf
2
yk1
P (k,k 1)
fme
,
0 k K 2
1 k K 1
g
k
(3)
y
k
Tf
2
yk
P (k,k 1)
fme
,
g
k
Trong đó: fm là tần số Doppler lớn nhất, Tf là
thời gian truyền của khung, k là xác suất trạng
thái ổn định được cho bởi phương trình sau:
yk
yk1
yk1
(4)
k
fy (y)dy e
e
y
k
Trong trường hợp BPSK, xác suất lỗi là
một hàm của SNR nhận được có thể được viết
như sau:
phối Beroulli với tham số
. Giả định rằng kết
quả của sự truyền dẫn là ngay lập tức có được
ở cuối của mỗi khe thời gian.
P 1 F( 2y)
(5)
Mô hình kênh truyền Markov trạng thái
hữu hạn (FSMC) như minh họa trong hình 1 mô
tả tính chất thay đổi theo thời gian của kênh
truyền fading vô tuyến. Trong kênh truyền
Rayleigh fading, SNR (y) tức thời nhận được
phân phối theo hàm mũ với hàm mật độ xác
suất:
m
F(x) là ký hiệu của hàm phân phối tích lũy CDF
của một biến ngẫu nhiên chuẩn hóa được cho
bởi phương trình sau:
x2
e 2 dx
(6)
1
F()
2
y
1
Với hàm mật độ xác suất của SNR trong
công thức (1), xác suất lỗi kí tự được viết dưới
dạng như sau
fy (y)
e
(1)
Với = E[y]. Đặt yi là ngưỡng của SNR nhận
được, trong đó 0 = y0 < y1 < y2 … <yK=∞. Kênh
được gọi là ở trạng thái gk, 0 ≤ k < K, nếu SNR
nhận được trong khoảng [yk, yk+1). Giả sử rằng
quá trình chuyển đổi trong mô hình FSMC xảy
ra tại ranh giới của khe thời gian trong đó một
khung có kích thước cố định được truyền đi và
sự thay đổi chỉ diễn ra giữa các trạng thái gần
nhau. Hơn nữa, độ lợi kênh truyền là hằng số
trong một khe thời gian của truyền dẫn. Các
y
yk1
1
e
1 F 2y dy
yk
P (gk )
(7)
b
y
yy
k1
1
e
dy
k
Công thức (7) theo chứng minh bài báo
[15] được viết lại như sau:
k k1
P (gk )
(8)
b
k
α
Trong đó:
α
1 - α
yk
α
k e 1 F 2yk
F
(9)
2yk ( 1)
1
α
α
α
I
D0
D1
---
DD
1 - α
1 - α
1 - α
3. LÝ THUYẾT TRÒ CHƠI
α
1 - α
3.1 Trò chơi ngẫu nhiên bị ràng buộc bởi
hàm chi phí
Truyền
Hoãn truyền
1 - α
1 - α
Trong mô hình này, tác giả xem xét một
mạng mà trong đó có khả năng lưu trữ nhiều
nhất một gói tin ở mỗi nút đối với các ứng dụng
đòi hỏi dữ liệu mới nhất. Như vậy khung hiện
tại trong bộ đệm được thay thế bằng một khung
mới đến. Độ nhạy thời gian trễ của gói tin được
mô hình hóa qua D khe thời gian cho mỗi khung.
Điều này có nghĩa rằng một khung có thời gian
dài hơn D khe thời gian phải được loại bỏ.
Trạng thái của hệ thống tại khe thời gian i được
kí hiệu như sau:
Hình 2. Sơ đồ trạng thái truyền dẫn với ràng
buộc trễ
Trong đó: P (gi , gi1) là xác suất chuyển đổi
g
trạng thái kênh từ gi đến gi1 và xác suất
chuyển đổi trạng thái nút P (ni ,ni1,a) được cho
n
bởi
P (I, I,.) (1
)
t
P (I, D0 ,.)
t
P (D , D ,0) (1 ),i 0,..., D 1
t
i
i1
(10)
xi gi ,n
(13)
i
P (DD , I,0) (1
)
t
Trong đó: gi là trạng thái kênh truyền tại khe
thời gian i, 0 ≤ gi < K và ni là trạng thái của nút
di động tại khe thời gian i. Trạng thái có thể có
của nút di động bao gồm I là trạng thái rỗi và
(D+1) trạng thái trễ trong đó D tương ứng thời
gian trễ tối đa của khung. Đặt I và Dk (k = 0,1,...,
D) biểu thị tương ứng trạng thái rỗi, (D+1) trạng
thái trễ. Nút di động được cho là ở trạng thái trễ
thứ k (được kí hiệu bằng Dk) khi khung bị trì
hoãn bởi k khe thời gian và ở trạng thái rỗi khi
không có khung tin. Đặt Ai(xi) là kí hiệu cho tập
hợp tất cả các hành động điều khiển có thể có
cho nút i ở trạng thái xi. ai là hành động điều
khiển được thực hiện tại khe thời gian i.
P (D , D0 ,.)
,i 0,..., D
t
i
P (D , I,1) (1 ),i 1,..., D
t
i
Dựa theo mô hình 2, tác giả [16] đã bỏ qua
các yếu tố nhiễu của môi trường vô tuyến đối
với hoạt động của các nút. Điều này đã thúc đẩy
chúng tôi nghiên cứu ảnh hưởng của nhiễu đến
xác suất truyền gói tin. Trong trường hợp nút
mạng sử dụng cơ chế truyền lại đối với các gói
tin lỗi với giả thiết gói tin có xác suất lỗi là Pf
và xác suất xung đột của các gói tin được giả
thiết là d. Các mô hình này sẽ mô tả cụ thể trong
hình 3 đối với mô hình chỉ xét đến cơ chế truyền
lại với xác suất lỗi gói tin do kênh truyền và
hình 4 với mô hình xét đến cơ chế truyền lại do
lỗi kênh truyền và xung đột gói tin.
Mỗi hành động trong tập A(xi) tương ứng
với các giá trị sau:
α
α
퐻표ã푛
푇푟푢푦ề푛
0,
1,
푎푖 = {
(11)
1 - α
α
α
α
P (ni ,ni1,a)
Đặt
kí hiệu xác suất chuyển
α
n
D0
D1
---
(1 - α )
DD
I
α
(1 - α)
ni
ni1
đến
đổi của nút di động từ trạng thái
(1 - α ).(1-Pf)
(1 - α ).Pf
dưới sự điều khiển hành động a theo sơ đồ trạng
thái thể hiện trong hình 2 [16]. Trong mô hình
này, các nút mạng không áp dụng cơ chế truyền
lại cho các gói tin lỗi và các nút mạng không có
thông tin về xác suất xung đột gói tin. Cho trạng
(1 - α ).Pf
(1 - α ).(1-Pf)
(1 - α )
(1 - α )
Truyền
Hoãn truyền
Hình 3. Sơ đồ trạng thái truyền dẫn với ràng
buộc trễ và truyền lại tập tin khi có lỗi kênh
truyền Pf
thái hệ thống
và hành động điều
khiển ai , xác suất của hệ thống đang ở trạng
thái trong khe thời gian tiếp
xi gi ,n
i
xi1 gi1,n
i1
Như hình 3, xác suất chuyển đổi trạng thái
nút P (ni ,ni1,a) được cho bởi
theo là:
n
Pr x | x ,a a P (g , g )P (n ,n ,a)
(12)
i1
i
i
g
i
i1
n
i
i1
P (I, I,.) (1
)
lỗi khung tin của kênh truyền. Pf (gi ) là xác
suất lỗi khung khi trạng thái kênh là gi . Giả
định lỗi bit độc lập, xác suất lỗi khung Pf (gi )
cho khung kích thước L và trạng thái kênh gi
có công thức như sau:
t
P (I, D0 ,.)
t
P (D , D ,0) (1
),i 0,..., D 1
t
i
i1
(14)
P (D , D ,1) (1
).P ,i 0,..., D 1
t
i
i1
f
P (DD , I,0) (1
)
t
P (D , D0 ,:)
,i 0,..., D
t
i
Pf (gi ) 1(1 P (gi ))L
(17)
b
P (D , I,1) (1 )(1 Pf ),i 1,..., D
t
i
Trong đó P (gi ) thu được từ công thức (8)
b
Trong đó Pf là xác suất lỗi kênh truyền
Để tránh lãng phí năng lượng, nút có thể
hoãn việc truyền tải bất cứ khi nào có thể với sự
chấp nhận được việc tràn bộ nhớ đệm. Với trạng
Hình 4 là mô hình trạng thái của nút thực
hiện truyền lại tập tin khi có lỗi khung tin Pf
và xung đột d. P (ni ,ni1,a) là kí hiệu xác suất
thái xit và hành động điều khiển
nhớ đệm của nút i cho bởi
a
it , tràn bộ
n
ni
chuyển đổi của nút di động từ trạng thái
ni1
đến
dưới sự điều khiển hành động a
∝, 푛푖푡 = 퐷푘 푣à 푎푖푡 = 퐻표ã푛
푙푡(푥푡, 푎푡) = {
(18)
theo sơ đồ trạng thái thể hiện trong hình 4.
푡
1, 푛푖 = 퐷퐷 푣à 푎푖푡 = 퐻표ã푛
푖
푖
푖
α
0,
퐾ℎá푐
α
1 - α
Trong đó
Cho
0 k D
α
α
α
ui (ai | xi )
kí hiệu của xác suất nút di
D0
(1 - α ).(1-Pf).(1-d)
D1
---
(1 - α )
DD
I
α
(1 - α)
động có hành động điều khiển a khi nút ở trạng
(1 - α ).Pf.d
x
i
biểu thị phân bố xác suất của trạng
thái
,
(1 -α) .Pf
(1 - α ).Pf.d
(1 - α ).Pf
i
thái khởi tạo xit0 . Ràng buộc kỳ vọng tràn bộ
(1 - α ).(1-Pf).(1-d)
đệm trung bình có thể được định nghĩa như sau
Truyền
(1 - α )
(1 - α )
Hoãn truyền
1 T 1
i
i
ii
const
(19)
L
limsup
E lt (xt ,at ) L
i
T
i,i
T
t0
Hình 4. Sơ đồ trạng thái truyền dẫn với ràng
buộc trễ, xác suất xung đột d, lỗi kênh truyền
u (u1,u2 ,...,uN )
Định nghĩa các vectơ
Pf
(1
,
2,...,N
)
và
tương ứng là tập hợp
Như hình 4, xác suất chuyển đổi trạng thái
các chiến lược và trạng thái phân phối xác suất
ban đầu cho tất cả các nút di động. Chi phí trung
bình cho mỗi giai đoạn của mỗi nút di động
được xác định như sau
nút P (ni ,ni1,a) được cho bởi
n
P (I, I,.) (1)
t
P (I, D0 ,.)
t
P (D , Di1,0) (1),i 0,..., D 1
1 T 1
t
i
Ei limsup
Eu e (xt ,at )
(15)
(20)
P (D , Di1,1) (1).P .d (1).P ,i 0,..., D 1
T
,u
i
t
i
f
f
T
t0
P (DD , I,0) (1)
t
Mục tiêu của mỗi nút là tìm ra chiến lược
P (D , D0 ,:) ,i 0,..., D
t
i
Ei
P (D , I,1) (1)(1 P )(1 d),i 1,..., D
ui
tối ưu
để đạt cực tiểu
(20) thoả điều
,u
t
i
f
Ei
kiện (19). Đặt
là giá trị tối ưu của OP. Một
Các chiến lược lựa chọn bởi tất cả các nút
di động xác định chi phí cho mỗi nút di động.
Ei Ei
quy tắc đạt được
gọi là tối ưu cho
,u
Dưới trạng thái hệ thống xt (x1t , x2t ,..., xNt ) và
OP. Kí hiệu Ui là tập tất cả các chính sách tối
các hành động điều khiển at (a1t ,a2t ,...,aNt ) của
ưu đó.
tất cả các nút di động tại thời điểm t, chi phí cho
mỗi nút di động được cho bởi công thức sau
3.2 Quy hoạch tuyến tính
ei (xt ,at ) ait {max (atj )+[1-max (atj )]Pf (git )}Ec
(16)
Một phương pháp giải quyết OP dựa trên
giải pháp của quy hoạch tuyến tính sẽ được
trình bày như bên dưới. Tầm quan trọng của
phương pháp này nằm ở thực tế là phương pháp
cũng cho phép xử lý các vấn đề tối ưu hóa với
j, ji
j, ji
Trong đó Ec là mức tiêu thụ năng lượng mỗi
khung. Trọng số
(0 1) , được sử dụng
để chỉ mối quan hệ của va chạm khung tin và
,
các ràng buộc bổ sung, trong đó các phương
pháp khác (dựa trên lập trình động) không áp
dụng được.
0 r x
1 r x
(27)
r (x)
4. KẾT QUẢ MÔ PHỎNG
Bảng 1. Các tham số mô phỏng
Chúng ta bắt đầu bằng mô tả phản ứng tối
ưu cố định cho nút i được tính toán cho một đa
ui
quy tắc cố định u. Sửa đổi quy tắc cố định
nút i. Chúng ta có công thức sau với mọi
Tham số
Số nút mạng
Thời gian truyền khung (Tf )
SNR trung bình
Giá trị
2-10
1ms
10dB
xi Xi
yi Xi
và
i
ui (ai | xi ) i
(21)
Kích thước gói tin (L)
Kích thước gói tin điều khiển 8 (bytes)
80 (bytes)
x u
y
x a
y
i
i
i
i
i
i
aiA (xi )
i
Tần số Doppler (fm)
Yếu tố trọng số trong hàm chi
phí ()
10Hz
0.5
Kí hiệu chi phí tức thời do nút khác i gây
ai
ra khi nút i sử dụng hành động điều khiển
và những nút khác sử dụng đa quy tắc cố định
ui
Bảng 1 tóm tắt giá trị các tham số được sử
dụng trong các thí nghiệm của tác giả. Trong
phần này, tác giả phân tích các đặc tính của mô
hình OTS và thực hiện các thí nghiệm khác
nhau để điều tra các đặc tính của mô hình OTS.
cho bởi phương trình sau
ej,u (xi ,ai )
u (a | x )lu (xl ) e (xt ,at )
(22)
i
l
l
l
i
(x,a)iKi
li
Trong đó: lu là xác suất trạng thái ổn định
(bất biến) của chuỗi Markov mô tả quá trình
trạng thái của nút i khi sử dụng quy tắc u,
e (xt ,at ) chi phí của nút di động i
i
Tập tất cả phản ứng tối ưu nút i dựa trên
ui
chính sách
có thể thu được bằng cách sử
dụng phương trình tuyến tính được định nghĩa
trong [14].
Hình 5. Ngưỡng truyền tối ưu theo phương
pháp truyền tải cơ hội trong điều kiện không
phụ thuộc khe thời gian trễ khi D=2 và
fm=5Hz
Phương trình tuyến tính (i,u): tìm
zi* :{zi*(x,a)}
(x,a)K
x,a , trong đó
i , sao cho
(23)
phương trình (22) nhỏ nhất
ej,u (x,a)zi (x,a)
i
(x,a)Ki
Thỏa điều kiện
[ (x)-i ]z (x,a) 0,r X
(24)
(25)
r
xar
i
i
xXi aA
i
l (x,a)z (x,a) L
i
i
const
xXi aA
i
(26)
zi (x,a) 0,(x,a)Ki ,
zi (x,a) 1
(x,a)Ki
Hình 6. Ngưỡng truyền tối ưu theo phương
pháp truyền tải cơ hội trong điều kiện không
phụ thuộc khe thời gian trễ khi D=2 và
fm=10Hz
Pxiar P .P
Trong đó
g
n
(x)
: hàm Kronecker delta là một hàm của hai
r
biến, thường chỉ là các số không âm. Hàm bằng
1 nếu các biến bằng nhau và bằng 0 nếu các biến
khác nhau:
Hình 5 và Hình 6 cho thấy các tác động của
kênh biến thiên theo thời gian lên ngưỡng
truyền tối ưu trong điều kiện không phụ thuộc
khe thời gian trễ. Như thể hiện trong Hình 5 và
Hình 6, các trạng thái kênh truyền được phân
chia thành bộ các trạng thái biểu diễn bởi các
tập B, M và G. Tập B chứa các trạng thái
Hình 7 và Hình 8 thể hiện tác động của
kênh truyền biến thiên lên ngưỡng truyền tối ưu
với các ràng buộc trễ (D). Khi điều kiện ràng
buộc độ trễ (D) trở nên thoải mái hơn, chiến
lược truyền tải tối ưu sẽ hội tụ đến hành động
hoãn truyền, dẫn đến ngưỡng truyền tăng lên.
Như minh họa ở Hình 7 và Hình 8, ngưỡng
ngưng và ngưỡng truyền tăng khi kênh truyền
biến thiên nhanh hơn hoặc thời gian trễ trở nên
không nhạy cảm. Quan sát này là trực quan vì
việc hoãn truyền để xem xét một kênh tốt hơn
là cần thiết để giảm chi phí của thất bại truyền
tải khi kênh fading biến thiên nhanh. Theo Hình
7 và Hình 8, mô hình OTS cải tiến truyền lại tập
tin lỗi có ngưỡng hoãn truyền và ngưỡng truyền
nhỏ hơn ngưỡng hoãn truyền và ngưỡng truyền
mô hình ban đầu, giúp cho gói tin được truyền
đi dễ dàng hơn trong khi vẫn đảm bảo số lần
truyền dẫn thành công giúp nâng cao hiệu suất
truyền dẫn
0 gk g
Dth trong đó kênh truyền ở trạng thái
và truyền dẫn luôn luôn bị hoãn. Các SNR
gDth
tương ứng đến
Tập M bao gồm các trạng thái
trong đó nút truyền gói với xác suất tối ưu p*
gTth
là ngưỡng hoãn truyền.
gDth gk gTth
và SNR tương ứng với
là ngưỡng truyền
tối ưu. Theo Hình 5 và Hình 6, mô hình OTS
cải tiến truyền lại tập tin lỗi có xác suất truyền
tối ưu lớn hơn so với xác suất truyền tối ưu mô
hình ban đầu do cơ chế cập nhật xác suất lỗi vào
trạng thái truyền dẫn của nút, góp phần hạn chế
hoãn truyền gói tin gây lỗi tràn bộ nhớ.
5. KẾT LUẬN
Đề tài trên đã phát triển mô hình truyền gói
tin cơ hội dựa trên lý thuyết trò chơi kết hợp
hàm chi phí để khảo sát các đặc tính của mô
hình OTS sử dụng cơ chế truyền lại tập tin và
mô hình OTS không sử dụng cơ chế truyền lại
tập tin, một chiến lược truyền thông cơ hội cho
các mạng vô tuyến có kênh truyền biến thiên
theo thời gian được rút ra. Đề tài đã tiến hành
nhiều thí nghiệm để quan sát và phân tích hành
vi của mô hình OTS qua lỗi tràn bộ đệm trong
phạm vi các ứng dụng nhạy với thời gian trễ.
Một chính sách truyền thông tối ưu được rút ra
cho sơ đồ OTS, mô hình OTS truyền lại tập tin
lỗi cho xác suất truyền tối ưu lớn hơn xác suất
truyền tối ưu mô hình không có cơ chế truyền
lại tập tin lỗi, trong đó nút di động chỉ bắt đầu
truyền khi chất lượng kênh vượt qua ngưỡng tối
ưu, do đó tránh được bất cứ sự truyền dẫn
không thành công gây lãng phí năng lượng và
giúp kéo dài thời gian hoạt động của mạng.
Hình 7. Ngưỡng truyền tối ưu theo phương
pháp truyền thông cơ hội phụ thuộc khe thời
gian trễ khi fm=10Hz và D=4
Hình 8. Ngưỡng truyền tối ưu theo phương
pháp truyền thông cơ hội phụ thuộc khe thời
gian trễ khi fm=10Hz và D=8
TÀI LIỆU THAM KHẢO
[1] S. Chakraborty, D. Dash, D. K. Sanyal, S. Chattopadhyay, M. Chattopadhyay, "Game-
theoretic wireless CSMA MAC protocols: Measurements from an indoor testbed," IEEE
Conference on Computer Communications Workshops (INFOCOM WKSHPS), 2016, pp.
1063 - 1064.
[2] M. Aliaskari, A. Shahzadi, "A game theoretic approach to joint resource management in
wireless ad hoc networks," in Proceedings of the 8th IEEE International Symposium on
Telecommunications (IST), 2016, pp. 6-11.
[3] O. Baig, Y. S. AI-Harthi, E. Al-Tubaishi, "Game-theoretic algorithm stimulating cooperation
in multi-hop wireless networks," in Proceedings of the 5th International Conference on
Game Theory for Networks, 2014, pp. 1-5.
[4] L. Chen, S. Low, and J. Doyle, "Contention control: A game-theoretic approach," in
Proceedings of the 46th IEEE Corference on Decision and Control (CDC 2007), Dec. 2007,
pp. 3428-3434.
[5] T. Cui, L. Chen, and S. Low, "A game-theoretic famework for medium access control," IEEE
J Set. Areas Commun., vol. 26, no. 7, pp. 1116-1127, September 2008.
[6] L. Zhao, J. Zhang, K. Yang, and H. Zhang, "Using incompletely cooperative game theory in
mobile ad hoc networks," in Proceedings of IEEE International Corerence on
Communications (ICC 2007), June 2007, pp. 3401-3406.
[7] L. Zhao, J. Zhang, and H. Zhang, "Gdcf: game-theoretic distributed co-ordination function
in wlans," Electronics Letters, vol. 43, no. 9, pp. 510-511,26 2007.
[8] L. Zhao, J. Zhang, H. Zhang, "Using incompletely cooperative game theory in wireless mesh
networks," IEEEIACM Trans. Netw., vol. 22, no. 1, pp. 39-44, Jan.-Feb. 2008.
[9] L. Jang-Won, T. Ao, H. Jianwei, M. Chiang, and A. Robert, "Rever-seengineering mac: A
non-cooperative game model," IEEE J Sel. Areas Commun., vol. 25, no. 6, pp. 1135-1147,
August 2007.
[10] M. Cagalj, S. Ganeriwal, I. Aad, and J.-P. Hubaux, "On selfish behavior in csma/ca
networks," in Proceedings of the 24th Annual Joint Corerence of the IEEE Computer and
Communications Societies (INFOCOM 2005), vol. 4, March 2005, pp. 2513-2524 vol. 4.
[11]
J. Konorski, "A game-theoretic study of csma/ca under a backoff attack," IEEE/ACM Trans.
Netw., vol. 14, no. 6, pp. 1167-1178, Dec. 2006.
[12] Y Jin and G. Kesidis, "Distributed contention window control for selfish users in ieee 802.11
wireless lans," IEEE J Set. Areas Commun., vol. 25, no. 6, pp. 1113-1123, August 2007..
[13] H. Inaltekin and S. Wicker, "The analysis of nash equilibria of the oneshot random-access
game for wireless networks and the behavior of selfish nodes," IEEE/ACM Trans. Netw., vol.
16, no. 5, pp. 1094-1107, Oct. 2008.
[14] E. Altmana, K. Avrachenkova, N. Bonneaua, M. Debbahc, R. EIAzouzid, and D. S.
Menaschee, "Constrained cost-coupled stochastic games with independent state processes,"
Operations Research Letters, vol. 36, no. 2, pp. 160-164, Mar. 2008.
[15] H. S. Wang and N. Moayeri, "Finite-state markov channel-a useful model for radio
communication channels," IEEE Trans. Veh. Technol., vol. 44,no. I,pp. 163-171, Feb. 1995..
[16] Ca Van Phan, "A game-theoretic framework for opportunistic transmission in wireless
networks," Proceeding of the International Conference on Communications and Electronics
(ICCE’14), Danang, Vietnam, July 2014.
Tác giả chịu trách nhiệm bài viết:
Họ tên: Nguyễn Chánh Tín
Đơn vị: Trường Đại học Sư phạm Kỹ thuật TP. HCM
Điện thoại: 093 262 29 73
Email: [email protected]
BÀI BÁO KHOA HỌC
THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ
Bài báo khoa học của học viên
có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn
Bản tiếng Việt ©, TRƯỜNG ĐẠI HỌC SƯ PHẠM KỸ THUẬT TP. HỒ CHÍ MINH và TÁC GIẢ
Bản quyền tác phẩm đã được bảo hộ bởi Luật xuất bản và Luật Sở hữu trí tuệ Việt Nam.
Nghiêm cấm mọi hình thức xuất bản, sao chụp, phát tán nội dung khi chưa có sự đồng ý
của tác giả và Trường Đại học Sư phạm Kỹ thuật TP. Hồ Chí Minh.
ĐỂ CÓ BÀI BÁO KHOA HỌC TỐT, CẦN CHUNG TAY BẢO VỆ TÁC QUYỀN!
Thực hiện theo MTCL & KHTHMTCL Năm học 2018-2019 của Thư viện Trường Đại học
Sư phạm Kỹ thuật Tp. Hồ Chí Minh.
9 trang
09/01/2024
20760
Free
Bạn đang xem tài liệu "Tối ưu cơ hội truyền gói tin trong mạng vô tuyến sử dụng lý thuyết trò chơi", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- toi_uu_co_hoi_truyen_goi_tin_trong_mang_vo_tuyen_su_dung_ly.pdf
