TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008

49

CẢI TIẾN CÁC THUẬT TOÁN MƯỢN VÀ KHOÁ
KÊNH TẦN SỐ MẠNG DI ĐỘNG TẾ BÀO
IMPROVING THE FREQUENCY CHANNEL BORROWING AND
LOCKING ALGORITHM IN CELLULAR MOBILE SYSTEM

ĐỖ HỮU TRÍ
Học viện Công nghệ Bưu chính, Viễn thông
VŨ DUY LỢI
Trung tâm Tin học - Văn phòng Trung ương Đảng
HÀ MẠNH ĐÀO
Viện Công nghệ Thông tin

TÓM TẮT
Trong bài báo này chúng tôi trình bày hai cải tiến trong cấp phát kênh tần số của mạng
di động tế bào. Bằng việc sử dụng hai ngưỡng nhằm phân loại các tế bào (ô) thành 3
lớp khác nhau, tiếp theo là định vị chính xác ô đồng kênh cần phải khoá kênh tần số, số
lượng ô đồng kênh cần phải khoá kênh tần số và gia tăng số kênh mà ô nóng có thể
mượn được từ ô lạnh. Kết quả cho thấy xác xuất khoá kênh của phương pháp mới
thấp hơn và số kênh mà ô nóng mượn được từ các ô lạnh cao hơn so với LBSB [2],
Adapt [4].
ABSTRACT
In this paper, we propose two reformations of channel frequency allocation in the
cellular mobile system. By using two thresholds to classify cellular in three difference
classes, we determine the co-channel cells that need to lock the channel frequency and
the number of co-channel cell have to be locked and increase the number of chanels
which a hot cell can borrow from a cold cell. Expriments have showed the proposal
method has a lower blocking probability and a higher borrowing channel than LBSB [2],

thuật toán mượn kênh và khoá kênh, theo đó ô nóng còn mượn kênh từ các ô khác nếu
chúng còn kênh rỗi, số ô phải khoá đồng kênh trong một số trường hợp chỉ cần 2 là đảm
bảo tránh được nhiễu đồng kênh. Các thuật toán này cũng sử dụng hai ngưỡng nóng và
lạnh. Mặt khác để tăng số kênh mà ô nóng có thể mượn được nhằm giảm hơn nữa số ô
nóng còn lại sau khi chạy thuật toán, các ô đồng kênh của ô cho mượn có thể khoá kênh
ở cho đến khi số kênh rỗi giảm xuống một mức thấp hơn ngưỡng lạnh nhưng vẫn đảm
bảo không gây ra hiệu ứng quả bóng bàn.
Nội dung bài báo được bố cục như sau: Phần hai sẽ trình bày tóm tắt những khái
niệm cơ bản nhất liên quan đến phân hoạch ô trong mạng tế bào. Phần ba đề xuất cải
tiến thuật toán mượn kênh tần số và khoá ô đồng kênh. Phần bốn trình bày về mô phỏng
và đánh giá kết quả. Phần năm là kết luận của bài báo.
2. Hệ thống thông tin đi động tế bào
2.1. Nhóm Compact

a) Tổ chức kết nối

b) Nhóm Compact (i=2, j=1)
Hình 1. Mạng di động tế bào
Mạng di động tế bào được tổ chức thành một tập hợp các ô lục lăng, mỗi ô được
phục vụ bởi một trạm điều khiển BS (Base Station) đặt tại trung tâm ô [1]. Tập hợp các
ô được liên kết với nhau tạo thành một trung tâm chuyển mạch (MSC) và hoạt động như
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008

51

một cổng của mạng tế bào kết nối tới các mạng viễn thông PSTN, ISDN hoặc mạng
máy tính LAN/WAN khác. Các BS kết nối với các thuê bao di động bằng đường truyền
vô tuyến và với MSC bằng đường truyền hữu tuyến (Hình 1-a).
Mỗi ô được cấp phát một tập kênh C, tập kênh này lại được tái sử dụng trong ô
khác với khoảng cách đủ để nhiễu đồng kênh gây ra là không đáng kể, khoảng cách này

trong khoảng thời gian cuối cùng ∝.
Thuê bao không phải là mới hoặc rời ô sẽ được phân thành lớp khác.
3. Đề xuất thuật toán mượn kênh và khoá kênh
Ô nóng sẽ chọn các ô lạnh để mượn kênh một cách ngẫu nhiên và mượn một tập
kênh mỗi lần như theo Adapt. Khi ô lạnh cho mượn kênh, các ô đồng kênh với nó phải
khoá tần số này lại để tránh nhiễu.
3.1. Xác định ngưỡng và phân lớp thuê bao
Ký hiệu c
i
là số kênh rỗi trong ô thứ i. Ở đây sẽ sử dụng 2 ngưỡng nóng h và
Hình 2. Phân lớp thuê bao
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008

52

lạnh l để phân loại các ô thành 3 lớp và 0≤ h ≤ l ≤ C. Ô có giá trị c
i
≥ l thì nó được gọi là
ô lạnh, nếu c
i
≤h thì đó là ô nóng, nếu l >c
i
> h thì nó được gọi là ô trung bình.
Ngưỡng lạnh l được xác định bằng trung bình cộng của số kênh rỗi của các ô
trong toàn mạng c
avr
, ngưỡng nóng h xác định bởi trung bình cộng của số kênh rỗi của
các ô mà có c
i
< c

Nếu cần mượn=0, Break hoặc nếu cần mượn=0>, tiếp tục bước tiếp theo.
 Bước 7. Thực hiện mượn kênh từ các ô cùng nhóm compact cho các thuê bao
còn lại. Khoá kênh. Break.
3.4. Xác định ô đồng kênh cần khoá
R là bán kính của mỗi ô, D là khoảng cách giữa 2 tâm của 2 ô, theo [3]:
D=(i
2
+ ij + j
2
)
1/2
. 3
1/2
. R = (3N)
1/2
. R (2)
Xét tham số shift giữa A và các ô đồng kênh của ô cho mượn kênh là (i
k
, j
k
) thì
dựa theo công thức (2) ta có:
D
k
= (3N
k
)
1/2
D
. R (3)

1, nếu ô nằm trên đường thẳng l
n
đường thẳng l
, thì khoá
đồng kênh ở ô n-1 và n. Nếu ô A nằm giữa 2
n
và l
n+1
Đối với các nhóm compact thuộc lớp 2, nếu ô A nằm trên đường thẳng l
thì khoá 3 ô đồng kênh n-1, n và n+1.
n
thì
khoá 3 ô đồng kênh n-1, n và n+1. Nếu ô A nằm giữa l
n
và l
n+1
4. Mô phỏng và đánh giá kết quả
thì khoá 2 ô đồng kênh n
và n+1.
Đối với các nhóm compact thuộc lớp 3, không thể định vị chính xác các ô cần
khoá kênh theo chỉ số n, do vậy sẽ sử dụng cách tính khoảng cách theo công thức pitago
trên mặt phẳng toạ độ hoặc biểu thức (4), (5). Một số trường hợp, ô đồng kênh cần khoá
chỉ cần là 2.
Các đề xuất đã được thử nghiệm trên chương trình mô phỏng, chương trình được
thiết kế bằng ngôn ngữ C và chạy trên môi trường C-Free. Chương trình mô phỏng sẽ
sản sinh ra kết quả là các tệp vết, có kích thước tăng tuyến tính khi phát sinh ô nóng
phải mượn kênh, theo các mô phỏng của chúng tôi, khi phát sinh ô thứ 36 nóng thì kích
cỡ tệp đã là 6,7Mb. Kết quả được so sánh với phương pháp LBSB và Adapt. Mạng có
190 ô, mỗi ô được cấp phát C=100 tần số, bán kính của ô là 1. Hai tham số shift nhận
giá trị 3 và 2, số ô N của nhóm compact là 19. Ngưỡng h nhằm xác định trạng thái nóng


1 18 5 6
Adaptive 23

3 18 52 18 12

23 16 50 13 3

51 3 5 2
TT mới 52

3 18 52 18 12

32 47 51 13 6

51 3 6 2

Ô nóng 80

91

106

108

111

118

125


2

15

7

8

12

5

LBSB 17

16

47

5

19

33

19

17

31


10

27

49

15

TT mới 26

36

49

5

43

16

47

19

12

36

11

Sau khi một ô lạnh cho mượn kênh, thì tần số này phải bị khoá ở các ô đồng
kênh, số lần phải khoá khi ô nóng mượn kênh như ở bảng 2:
Bảng 2. Số lần khoá ở ô ô đồng kênh
Ô nóng 0 11 18 24 25 32 35 55 59 60 64 66 68 71 74
LBSB 60 0 0 99 0 0 0 96 96 0 93 0 45 0 18
Adaptive 2 0 0 40 0 0 17 3 66 0 0 24 0 0 4
TT mới 15 0 0 27 0 0 26 58 67 0 7 36 0 2 3

Ô nóng 80 91 106 108 111 118 125 126 129 139 147 169 180 186
LBSB 0 0 90 0 0 68 18 0 116 84 90 60 63 0
Adaptive 15 42 12 0 23 0 51 0 12 19 9 19 49 10
TT mới 18 60 33 0 26 0 102 4 20 42 8 40 22 11

Hình 5. Số lần khoá kênh của phương pháp mới và LBSB.
Ta thấy, trong hầu hết các trường hợp ô nóng mượn kênh, mặc dù số kênh mượn
được lớn hơn nhưng số lần phải khoá kênh trong thuật toán mới bao giờ cũng thấp hơn
so với thuật toán LBSB.
Khoá kênh theo phương pháp mới và Adapt: Số ô phải khoá đồng kênh trong
thuật toán Adapt bao giờ cũng là 3, đối với thuật toán mới trong một số trường hợp chỉ
cần 2 là đủ. Như đã trình bày ở trên, trong tất cả các trường hợp, số lượng kênh mà ô
nóng mượn được trong thuật toán mới bao giờ cũng lớn hơn so với trong thuật toán
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008

56

Adapt nên nhiều khi số lần khoá kênh ở thuật toán mới lớn hơn số lần khoá đồng kênh ở
thuật toán Adapt.
4.3. Điều chỉnh ngưỡng khoá đồng kênh
Để tăng cường thêm số kênh cho mượn, làm giảm bớt số ô nóng, chúng tôi điều
chỉnh đối với các ô đồng kênh, ngưỡng khoá kênh thấp hơn giá trị ng ưỡng lạnh. Khi

Communications Magazine, vol 3, No 2, pages 10-31. June 1996.
[2] Sajal K.Das, Sanjoy K.Sen, Rajeev Jayaram. A Dynamic Load Balancing Strategy
for Channel Assignment Using Selective Borrowing in Cellular Mobile
Environment. Wireless Networks, volume 3, page 333-347, 1997.
[3] V. H. Mac Donald. Advanced Mobile Phone Service: The Cellular Concept. The
Bell System Technical Journal, volume 58, number 1 (1979), pages 15-41.
[4] Yongbing ZHANG. A New Adaptive Channel Assignment Algorithm in Cellular
Mobile Systems, Proc 32 nd Hawaii International Conference on System Science
TẠP CHÍ KHOA HỌC VÀ CÔNG NGHỆ, ĐẠI HỌC ĐÀ NẴNG - SỐ 6(29).2008

57

1999.