Thuật Toán Cân Bằng Tải Động Mượn Kênh Chọn Lọc (Lbsb)

nào mượn được nhiều kênh mà số tế bào đồng kênh phải khoá kênh là ít nhất, số tế bào bị khoá mà chuyển thành trạng thái “quá tải” là ít nhất mà không gây nhiễu cho các kênh sử dụng khác. Có nhiều thuật toán mượn/khoá kênh đã được đề xuất và mỗi thuật toán đều có những ưu, nhược điểm riêng. Sau đây luận án sẽ khảo sát một số thuật toán mượn, khoá kênh tiêu biểu để nâng cao chất lượng dịch vụ của mạng hoặc để thực hiện cân bằng tải động của mạng.

1.4.2. Thuật toán mượn, khoá kênh đơn giản

Thuật toán mượn, khoá kênh được đề xuất lần đầu tiên (1993) có tên là là mượn kênh đơn giản SB [15][24]. Trong thuật toán này, khi yêu cầu cuộc gọi đến một tế bào và ở đó không còn kênh danh định nào rỗi nữa, trạm gốc có thể mượn một kênh từ tế bào lân cận để phục vụ yêu cầu cuộc gọi miễn là kênh này không gây nhiễu cho các cuộc gọi hiện thời. MSC giám sát thủ tục mượn kênh theo một thuật toán chú trọng tới kênh của các tế bào có lưu lượng thấp. Vì lý do nhiễu đồng kênh nên những tế bào có khoảng cách so với tế bào mượn kênh từ một đến hai tế bào mà có kênh danh định cùng tần số với kênh đã mượn sẽ không được sử dụng, do vậy, MSC sẽ khóa kênh ở những tế bào này. MSC lưu trữ dữ liệu về những kênh rỗi, đang phục vụ, đã cho mượn và đã khóa đồng thời MSC cũng phải mở rộng khả năng lưu trữ tại MSC để phục vụ việc cần thiết phải tìm kiếm dữ liệu. Thuật toán SB đem lại khả năng khóa cuộc gọi thấp hơn FCA dưới điều kiện lưu lượng thấp và trung bình. Tuy nhiên, trong điều kiện mật độ lưu lượng lớn, việc mượn kênh có thể tăng nhanh đến mức mà hiệu quả sử dụng kênh bị suy giảm nghiêm trọng, do tốc độ khoá kênh gia tăng nhanh chóng, kết quả cho thấy FCA thực hiện tốt hơn SB ở điều kiện lưu lượng lớn. Thuật toán mượn kênh đơn giản tiêu biểu là thuật toán mượn kênh có khoá kênh và mượn kênh không khoá kênh. Thuật toán mượn kênh có khoá kênh sử dụng chiến lược mượn kênh có khóa kênh [15][16][17] nhằm mượn kênh từ tế bào liền kề nhưng ngăn cản hoàn toàn hoặc một phần việc sử dụng kênh đã được mượn trong các tế bào đồng kênh với tế bào cho

mượn mà gần với tế bào mượn để tránh nhiễu đồng kênh. Ví dụ như trong hình 1.8, Khi tế bào P mượn kênh x từ tế bào A1 để phục vụ cuộc gọi trong P, tế bào A2 và A3 là những tế bào đồng kênh với A1 sẽ không được phép dùng kênh x nữa vì nó nằm trong phạm vi nhiễu đồng kênh của P. Từ đó kênh x trong các tế bào đồng kênh này phải được khoá để tránh nhiễu cho tế bào P khi P đang sử dụng kênh mượn x từ A1.

Có thể bạn quan tâm!

Xem toàn bộ 149 trang tài liệu này.

Hình 1.8: Mượn kênh và khoá kênh

Khóa kênh làm giảm dung lượng của mạng. Để khắc phục trở ngại này, một số thuật toán được bổ sung thêm các chiến lược tái gán kênh. Tái gán kênh là một chuyển giao bên trong tế bào, tức là thuê bao được yêu cầu thay đổi tần số đang sử dụng hiện thời sang một tần số khác dưới sự điều khiển của cùng trạm gốc. Tái gán kênh được coi như là cách làm giảm khả năng khóa kênh và làm cực đại việc tái sử dụng kênh. Trái lại trong thuật toán mượn kênh không khoá kênh sử dụng chiến lược mượn kênh không khóa (CBWL) [7][8][9][32][45] từ những tế bào lân cận, theo cách này, kênh đi mượn được sử dụng cùng với việc giảm công suất phát để tránh nhiễu với các tế bào đồng

kênh của tế bào cho mượn mà gần với tế bào mượn (trong phạm vi khoảng cách tái sử dụng đồng kênh).

1.4.3. Các thuật toán mượn, khóa kênh lai ghép

Vấn đề chính của thuật toán SB là không có sự điều khiển về số lượng kênh mà mỗi tế bào có thể cho mượn. Trong thuật toán mượn kênh lai ghép đơn giản SHCB [6][32], tập các kênh được gán cho một tế bào được chia làm 2 nhóm A và B. Nhóm A là là các kênh nội bộ chỉ được sử dụng để phục vụ yêu cầu cuộc gọi bên trong ô. Các tế bào lân cận có thể mượn các kênh của nhóm B là nhóm gồm các kênh “có thể mượn”. Tỉ số A:B được coi là khả năng cho mượn.

Thuật toán mượn với sắp xếp kênh (BCO) cũng chia kênh danh định thành 2 nhóm nhưng tỉ số giữa kênh nội bộ và có thể mượn là động và phụ thuộc vào điều kiện lưu lượng hiện thời. Các kênh trong tế bào được sắp xếp theo cách: Kênh đầu tiên có thứ tự ưu tiên cao nhất để gán cho cuộc gọi phát sinh đi hoặc đến trong tế bào, kênh cuối cùng có thứ tự ưu tiên cao nhất trong việc cho các tế bào lân cận mượn. Mỗi lần thực hiện cuộc gọi, kênh thích hợp nhất trong số tất cả các kênh rỗi sẽ được chọn. Nếu trạm gốc thực hiện chức năng này, MSC cần thiết được thông báo về kết quả gán. MSC sử dụng thuật toán tương ứng để tính toán và cập nhật khả năng mỗi kênh được mượn dựa trên các điều kiện về lưu lượng. Nếu kênh là rỗi ở trong 3 tế bào đồng kênh gần nhất thì chỉ khi đó kênh mới thích hợp đối với việc cho mượn. Để làm tăng kênh có sẵn dành cho việc mượn hoặc khóa, một số phiên bản của thuật toán BCO có thêm việc tái gán kênh. Khi một kênh có thứ tự ưu tiên cao được giải phóng, kênh này được tái cấp phát cho một thuê bao hiện thời đang sử dụng kênh có thứ tự ưu tiên thấp nhất.

Mượn với khóa kênh định hướng (DBCL) tương tự như thuật toán BCO có tái gán kênh. Tuy nhiên thuật toán DBCL sử dụng cách thức khóa kênh hiệu quả. Khi một kênh bị khóa, nó chỉ bị khóa ở những hướng mà sẽ gây ra nhiễu đồng kênh. Các tế bào đã định vị vô hướng có thể mượn hoặc khóa kênh.

Thuật toán SHCB thực hiện tốt hơn FCA trong trường hợp lưu lượng thấp và trung bình. Dưới điều kiện tải lớn, điểm mà SHBC làm tốt hơn FCA sẽ phụ thuộc vào tỉ số A:B. Theo kết quả mô phỏng thì các thuật toán BCO và DBCL thực hiện tốt hơn FCA trong mọi điều kiện về lưu lượng. Thuật toán DBCL thực hiện tốt hơn BCO và cũng là một thuật toán cấp phát kênh động gọi là chiến lược gán kênh địa phương động (LODA). Bằng việc kết hợp khóa kênh định hướng và tái gán kênh, DBCL đã làm gia tăng việc tái sử dụng kênh.

1.4.4. Thuật toán thử trực tiếp

Trong thuật toán thử trực tiếp, giả thiết là có vùng phủ sóng chồng lấn giữa các tế bào mà ở vùng này các thuê bao có thể thu được chất lượng tín hiệu phát từ tế bào lân cận tốt gần như là trong tế bào hiện thời . Khi một thuê bao thử thiết lập cuộc gọi và không còn kênh rỗi nào nữa [11] hoặc các kênh bị chiếm giữ đã đạt tới một ngưỡng xác định, MSC có thể chỉ dẫn một vài thuê bao của tế bào kiểm tra chất lượng tín hiệu phát các kênh từ các tế bào lân cận. Thuê bao nào mà nhận được chất lượng tín hiệu phát có thể chấp nhận được từ một tế bào lân cận, một yêu cầu chuyển giao sẽ được thiết lập đối với tế bào này và thuê bao được chuyển miễn là tế bào này có đủ kênh rỗi để cấp phát một kênh theo yêu cầu của thuê bao. Bằng cách này, tế bào mà có lưu lượng cao có thể có một số kênh danh định vừa được tự do và sử dụng chúng cho các yêu cầu cuộc gọi mới.

1.4.5. Thuật toán cân bằng tải động mượn kênh chọn lọc (LBSB)

Ý tưởng chính của thuật toán cân bằng tải động mượn kênh chọn lọc LBSB là chuyển các kênh từ một tế bào có các kênh có sẵn được gọi là “ô lạnh” sang một tế bào quá tải được gọi là “ô nóng” [29][30][31]. Nguyên tắc cơ bản của việc mượn kênh là: khi một tế bào không còn đủ kênh có sẵn để gán cho yêu cầu thiết lập cuộc gọi, gọi là tế bào quá tải hay “ô nóng”, cần xác định các tế bào tải nhẹ xung quanh, còn gọi là “ô lạnh”, một cách thích hợp, để mượn kênh còn sẵn. Như vậy, một tế bào nóng không

được cho mượn kênh; việc mượn kênh được ưu tiên cho các tế bào nóng, và các thuê bao đang rời khỏi tế bào nóng này được ưu tiên sử dụng kênh được mượn. Một tế bào lạnh không được phép mượn kênh; không phải tế bào lạnh nào cũng có thể cho mượn kênh có sẵn, và việc cho mượn kênh có thể làm cho tế bào lạnh trở thành tế bào nóng.

Chính vì vậy, phải xác định các tiêu chí để lựa chọn các tế bào lạnh một cách phù hợp, đó là:

a) Độ lạnh của một tế bào lạnh L gọi là dc(L) là tỉ số giữa số kênh có sẵn và tổng C kênh của tế bào đó. Một tế bào được xác định là nóng hoặc lạnh phụ thuộc vào độ lạnh dc: nếu dc nhỏ hơn hoặc bằng một ngưỡng h xác định thì đó là tế bào nóng, ngược lại sẽ là tế bào lạnh. Việc xác định h phụ thuộc vào trung bình tỷ lệ các cuộc gọi đến và tỷ lệ cuộc gọi được kết thúc của toàn mạng. Các giá trị của h thường là 0,2 hoặc 0,25.

b) Khoảng cách gần D(B,L) là khoảng cách giữa tế bào cần mượn kênh B và tế bào cho mượn kênh L (tính bằng số ô).

c) Số tế bào nóng bị khóa H(B,L) là số tế bào nóng đồng kênh của tế bào cho mượn L và không đồng kênh với tế bào cần mượn kênh B.

Như vậy, một tế bào lạnh phù hợp cho mượn kênh là tế bào có độ lạnh dc(L) cao, khoảng cách gần D(B,L) nhỏ và số tế bào nóng bị khóa H(B,L) nhỏ. Tế bào lạnh được chọn để cho mượn kênh trong nhóm các tế bào lạnh phù hợp cho mượn kênh là tế bào có giá trị hàm F(B,L) là lớn nhất [16]:

F (B, L) 

D(B, L) RCP

dc (L)

1 H (B, L) ( )

(1.4)

Ở đây RCP là bán kính tính theo đơn vị là ô của nhóm compact và 1≤ D(B,L)

≤Rcp, 0≤ H(B,L) ≤ 6. Tham số RCP và 7 được dùng làm chuẩn hoá. Từ đó số kênh mượn từ tế bào lạnh X được xác định bởi phương trình (1.5):

X= C.(dcavr - (1.5)

Giá trị ngưỡng h được xác định từ hệ phương trình (1.6) [30]:

(1h )C 1 l'( hC 1)

 1 l'

ph 1 l(1h )C 1

(1h )C '

l l

1 l' hC

(1.6)





b 6

1 l

6i

1 l'



iph(1 ph) p

i0

Với ph là xác suất của tế bào chuyển thành nóng; l =pf/pr , l’ =p’f/p’r với pf là xác xuất chuyển về phía trước của tế bào lạnh, p’f là xác xuất chuyển về phía trước của một tế bào nóng, pr là xác xuất chuyển ngược của tế bào lạnh và p’r là xác xuất chuyển ngượi của tế bào nóng trong mô hình Makov đối với tế bào.

Việc cân bằng tải được thực hiện nhờ việc di chuyển một số kênh từ tế bào lạnh sang tế bào nóng theo một nguyên tắc nhất định. Sau đó, việc gán kênh được thực hiện trên cơ sở phân loại thuê bao trong một tế bào thành 3 loại: a) thuê bao mới, b) thuê bao đang rời ô, và c) thuê bao khác; từ đó tạo thành 4 lớp ưu tiên khác nhau đối với yêu cầu thiết lập cuộc gọi của 3 loại thuê bao nói trên. Kết quả mô phỏng [30] cho thấy thuật toán LBSB hoạt động hiệu quả hơn các thuật toán cân bằng tải khác như thử trực tiếp.

1.4.6. Thuật toán cân bằng tải động mượn kênh chọn lọc phân tán (D-LBSB)

Nguyên tắc hoạt động cơ bản của thuật toán cân bằng tải động với mượn kênh chọn lọc phân tán D-LBSB dựa trên thuật toán cấp phát kênh cố định FCA [17]. Một tế bào được xác định là nóng, nếu độ lạnh của tế bào nhỏ hơn hoặc bằng giá trị ngưỡng xác định h nào đó. Trường hợp ngược lại thì tế bào được xác định là lạnh. Thuật toán D-LBSB cho phép sử dụng kênh rỗi của một tế bào lạnh cho một tế bào nóng thông qua cơ chế mượn kênh phân tán, nghĩa là, trạm điều khiển của một tế bào (bất kỳ) có khả năng thực hiện thuật toán mỗi khi tế bào quá tải với yêu cầu cấp phát kênh (ô nóng).

Trong khi thuật toán LBSB được kích hoạt thực hiện ở thiết bị điều khiển trung tâm MSC theo chu kỳ xác định thì thuật toán D-LBSB được thực hiện đồng thời ở tất cả tế bào nóng. Như vậy, D-LBSB phản ứng nhạy cảm hơn thuật toán LBSB với yêu cầu tải cấp phát kênh thay đổi đột biến tại chính nơi xảy ra đột biến tải, hay chính là tế bào nóng. Lưu ý rằng, hiệu quả hoạt động của thuật toán tập trung LBSB phụ thuộc vào việc lựa chọn chu kỳ kích hoạt thuật toán này ở trạm điều khiển trung tâm MSC; chu kỳ này cần được xác định mềm dẻo: là chu kỳ ngắn nếu tải thay đổi thường xuyên; là chu kỳ dài nếu hệ thống ổn định với một mức tải nhất định.

Thuật toán phân tán D-LBSB cũng có vấn đề của nó. Do thuật toán được kích hoạt đồng thời ở tất cả các tế bào nóng, có thể dẫn đến tình trạng là nhiều yêu cầu cấp phát kênh từ nhiều tế bào nóng được xử lý bởi một tế bào lạnh. Có thể giải quyết vấn đề này bằng việc gán cho các yêu cầu khác nhau thứ tự ưu tiên khác nhau và việc xử lý yêu cầu cấp phát kênh được thực hiện theo thứ tự ưu tiên xác định. Một vấn đề khác là, khi một kênh được cấp phát, tế bào cho mượn kênh cần biết giá trị hàm F(B,L) của tất cả các tế bào trong nhóm compact. Giá trị hàm F(B,L) có thể thay đổi với mỗi tế bào khi kênh được cho mượn từ tế bào đó bởi tế bào nóng thực hiện thuật toán D-LBSB đồng thời.

1.4.7. Thuật toán mượn, khóa kênh thích nghi

Thuật toán do tác giả Yongbing ZHANG đề xuất [7], nhằm cải tiến những nhược điểm của LBSB. Điểm khác biệt cơ bản ở đây là: hệ thống sử dụng 2 ngưỡng, ngưỡng nóng và ngưỡng lạnh để phân loại các tế bào trong hệ thống thành 3 lớp tương ứng với trạng thái của tế bào - cũng chính là số kênh rỗi trong tế bào, đó là tế bào lạnh, tế bào trung bình và tế bào nóng (Hình 1.9). Điều này cho trạng thái tế bào liên tục chuyển từ nóng sang lạnh và ngược lại. Tế bào nóng chỉ được phép mượn kênh từ tế bào lạnh, và tế bào lạnh chỉ giới hạn việc cho mượn kênh đối với các tế bào nóng. Còn tế bào trung bình không được phép mượn cũng như cho mượn kênh.

Hình 1.9: Phân loại tế bào lạnh, tế bào trung bình và tế bào nóng

Việc xác định ngưỡng được thực hiện như sau: Ký hiệu ci là số kênh rỗi trong tế bào thứ i, 2 ngưỡng nóng Th và lạnh Tl để phân loại các tế bào thành 3 lớp khác nhau, 0≤ Th ≤ Tl ≤ C. Nếu số kênh rỗi trong tế bào i bằng hoặc lớn hơn ngưỡng lạnh tức là ci≥Tl thì nó được gọi là tế bào lạnh, nếu số kênh rỗi của tế bào i nhỏ hơn hoặc bằng ngưỡng nóng, tức ci≤ Th thì đó là tế bào nóng, nếu Tl>ci>Th thì nó được gọi là tế bào trung bình. Ngưỡng lạnh Tl được xác định bằng trung bình cộng của số kênh rỗi của các tế bào trong toàn mạng cavr, ngưỡng nóng Th = Tl - ∆lh, với ∆lh>0 và Th> cmin, cmin là giá trị nhỏ nhất mà Th có thể nhận được. Giá trị của ngưỡng lạnh thay đổi tuỳ thuộc vào trạng thái của toàn bộ hệ thống. tế bào nóng được phép mượn kênh từ các tế bào lạnh nhưng tế bào lạnh không được phép mượn kênh. tế bào trung bình không được phép mượn hoặc cho mượn kênh.

1.5. Nhận xét các thuật toán mượn, khóa kênh

Từ việc khảo sát các thuật toán mượn khóa kênh truyền thống, luận án cho thấy đa số các thuật toán truyền thống đều sử dụng giá trị ngưỡng để phân biệt trạng thái tải của tế bào. Điều này dễ gây cho hệ thống mất ổn định vì trạng thái tải của các tế bào dao động xung quanh ngưỡng (hiệu ứng quả bóng bàn) và truyền các thông điệp không cần thiết. Mặt khác việc xác định giá trị ngưỡng quá phức tạp và tốn thời gian, số cuộc gọi tới và thời gian thực hiện cuộc gọi không biết trước, vì vậy cần có một cơ chế dự báo phù hợp hơn, hiệu quả hơn. Trong luận án này sẽ đề xuất một cơ chế mới để giải quyết vấn đề trên hiệu quả hơn: phương pháp mượn, khóa kênh trên cơ sở bộ điều khiển thông minh. Phương pháp mới này cho phép khắc phục được hạn chế của các