glj.m

GLJ调度算法的实现

function [schedultable,schedullen,bandsize,minbandwith,matrixnumb]=glj(T)

N=4;   %%  4×4端口交换机
T=[16,8,15,13;23,9,14,14;4,29,8,6;15,12,21,25];%% 对给定的流量矩阵 T 而言  
%%%%%备份原流量矩阵T    
    backupT=T;
    T1=T;
    T2=T;
    constbackT=T;
    
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%     计算最小需求带宽minbandwith      %%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 minbandwith=0;%%% 表示最小需求带宽   
 g=zeros(1,N);  %g[N]存放T的各列按降序排列后每行的最大值
 h=zeros(1,N);  %h[N]存放T的各行按降序排列后每列的最大值
%%%%%%%  对T的列向量进行冒泡排序,按降序排列 
for j=1:N     
    for k=1:N-1  
        for i=1:N-k
            if T1(i,j)<T1(i+1,j)
                temp=T1(i,j);
				T1(i,j)=T1(i+1,j);
				T1(i+1,j)=temp;
            end
        end
    end
end
T1
%%%%%%%%%%%%%%   计算流量矩阵 T 的最小需求带宽    %%%%%%%%%%%
    %找出每行的最大值存入g[i]中
    for i=1:N 
        for j=1:N
            if T1(i,j)>g(i)
                g(i)=T1(i,j);
            end
        end
    end
    g
    %对T的行向量进行冒泡排序,按降序排列
    for i=1:N  
        for k=1:N-1
            for j=1:N-k
                if T2(i,j)<T2(i,j+1)
                    temp=T2(i,j+1);
                    T2(i,j+1)=T2(i,j);
                    T2(i,j)=temp;
                end 
            end
        end
    end 
    T2
 %找出每列的最大值存入h[i]中
 for j=1:N  
     for i=1:N
         if T2(i,j)>h(j)
             h(j)=T2(i,j);
         end
     end
 end  
 h
   tempminbandwith=0;   
   for i=1:N
       tempminbandwith=tempminbandwith+g(i);
   end
   minbandwith=0;
   for i=1:N
       minbandwith=minbandwith+h(i);
   end
   if tempminbandwith>minbandwith
       minbandwith=tempminbandwith;
   end
   fprintf('最小需求带宽等于');minbandwith

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%       
%%%%%%%                      下面进行GLJ分解                     %%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
   T=[16,8,15,13;23,9,14,14;4,29,8,6;15,12,21,25];
   BANDWITH=2; %% 预先分配得到的调度矩阵的个数为2，后面matlab可以根据实际数修改 
   p=zeros(N,N,BANDWITH);%三维矩阵p保存分解的排列矩阵，预先附值为全零矩阵   
    for i=1:N*N
        L(i)=0;   %%%% 用 L 行向量存储矩阵T中的所有元素，预赋值为全零
        index(i)=0;%% 用向量index存储与L中的各个元素对应的在T(i，j）的坐标，index＝10*i+j
    end    
    %%%%    对L向量中的元素按降序排列,（插入排序法）   %%%%%%%
    z=1;
    switchtag=0;
    for i=1:N
        for j=1:N
            if i==1&j==1
                L(z)=T(i,j);
                index(z)=10*i+j;
            else
                for k=1:z-1
                    if L(k)<T(i,j)
                        switchtag=1;
                        break;
                    end
                end
                if switchtag==1
                    switchtag=0;
                    m=z-1;
                    while m~=k-1
                        L(m+1)=L(m);
                        index(m+1)=index(m);
                        m=m-1;
                    end 
                    L(k)=T(i,j); 
                    index(k)=10*i+j;
                else
                    L(z)=T(i,j);
                    index(z)=10*i+j;
                end                  
            end            
            z=z+1;
        end
    end    
    L,index
    
    %%%   按L中元素的降序并满足无冲突条件，循环进行矩阵分解，直到T=0 %%%%%%%%
    bandsize=0;% 业务矩阵调度的需求带宽 
    matrixnumb=0; %存放分解得到的排列矩阵的个数 
    notzerotag=1;   %表示 T 是否为全零的标记，＝0为全零矩阵
    
    schedultag=zeros(1,N*N); %设置各个元素的调度标记，赋初值＝0表示未被调度   
    zeronumber=0;
    for i=1:N*N
        if L(i)==0            
            zeronumber=zeronumber+1;
        end
    end
    linei=zeros(1,4);  %存放排列矩阵元素的行坐标
    columj=zeros(1,4); %存放排列矩阵元素的列坐标  
    number=0; %计数器    
    while notzerotag          
        conflictag=zeros(1,N*N);         
        j=1;
        i=1;
        while j<=N                                         
            while (i<N*N & schedultag(i)==1)|conflictag(i)==1
                i=i+1;
            end     
            if matrixnumb==3
                a=1;
            end
            if j==1
                columj(j)=mod(index(i),10);
                linei(j)=(index(i)-columj(j))/10;
                schedultag(i)=1;
                number=number+1;
                temp=L(i);
              linei(j);columj(j);
                j=j+1;                
            else
                tempj=mod(index(i),10);
                tempi=(index(i)-tempj)/10;
                for k=1:j-1
                    if tempj==columj(k)|tempi==linei(k)
                        conflictag(i)=1; 
                        break;        
                    end         
                end
                if conflictag(i)==0
                    columj(j)=tempj;
                    linei(j)=tempi;
                    schedultag(i)=1;
                    number=number+1;
                 linei(j);columj(j);
                    j=j+1;
                    if L(i)>temp %%找置换矩阵中元素最大值作为其系数
                        temp=L(i);
                    end
                else
                    if i==N*N-zeronumber
                        for t=j:N
                            columj(t)=0;
                            linei(t)=0;
                        end
                        break;
                    end 
                end 
                if number==N*N-zeronumber
                    notzerotag=0;
                    for t=j:N
                        columj(t)=0;
                        linei(t)=0;
                    end
                    break;
                end                 
            end                       
        end        
        matrixnumb=matrixnumb+1;
        minq(matrixnumb)=temp;%minq[] 存放分解得到的排列矩阵的系数
        for k=1:N
            if linei(k)~=0&columj(k)~=0
                p(linei(k),columj(k),matrixnumb)=1;
                T(linei(k),columj(k))=0;
            end        
        end        
    end
        fprintf('LJ分解共得到排列矩阵个数为：');matrixnumb        
        fprintf('个矩阵的系数分别为');minq
        for i=1:matrixnumb
            bandsize=bandsize+minq(i); 
        end
        fprintf('\n实际的需求带宽等于');bandsize  
         fprintf('\n得到的排列矩阵如下 ');p
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%下面对p[i][j][t]进行LJ调度 得到调度表schedul[N][t],每一列对应一个时隙的调度
%LJ调度与BV调度的区别是考虑了调度的开始时间starttime
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
t=matrixnumb;
V=minbandwith;%%  V表示设交换机速率
for i=1:t 
    selecttag(i)=minq(i);   %对t个标记的被选择标记附初值＝0：被调度完，~=0：未被调度完 
    minq(i)=minq(i)/V;  %计算各排列矩阵的权重＝系数/V;
    tagclass(i)=1/minq(i);  %t个排列矩阵的标记类的值
    select(i)=tagclass(i);   %t个排列矩阵的初始完成时间 
    starttime(i)=0;      %对t个标记的开始时间赋初始值为1； 
end 
selecttag,select,starttime

for k=1:bandsize 
    minfinishtime=100; %%设完成时间的最小值，附随机初值为100
    mintag=1;%mintag表示设完成时间最小的排列矩阵的下标,附随机初值为1
    notadaptnumb=0;
    finishnumb=0;%%%表示被调度完成的排列矩阵的个数
    for i=1:t
        if selecttag~=0&starttime(i)<=k
            if (select(i)<minfinishtime)
                mintag=i;
                minfinishtime=select(i);
            end
        %%%%jia   
        elseif selecttag(i)==0
            finishnumb=finishnumb+1;
            continue;         
        else 
            notadaptnumb=notadaptnumb+1;
        %%%%%jia 
        end
    end   
    %%%jia
    if notadaptnumb==t-finishnumb
        minfinishtime=100;
        for j=1:t
            if (select(j)<minfinishtime)
                mintag=j;
                minfinishtime=select(j);
            end
        end
    end
    %%%jia
    
	%% 下面对p[][][mintag]调度
    for i=1:N
        for j=1:N
            if p(i,j,mintag)==1
				schedul(i,k)=j;
            end
        end
    end
    %修改被调度的排列矩阵的标记
    starttime(mintag)=select(mintag);
	select(mintag)=select(mintag)+tagclass(mintag);
	selecttag(mintag)=selecttag(mintag)-1;
    k,starttime,select,selecttag
end
       fprintf('\n得到的调度矩阵如下');
       schedul        
    
  %修改得到的调度表,删除冗余调度使其等于原流量
     for i=1:N
         for j=1:bandsize 
             if schedul(i,j)~=0
                 temp=schedul(i,j); 
                 if backupT(i,temp)>=1	
                     backupT(i,temp)=backupT(i,temp)-1;
                 else
                     schedul(i,j)=0;
                 end
             end
         end
     end 
     fprintf('\n删除冗余调度后得到的调度矩阵如下');schedul 
 
  %%%%  删除全零调度向量
  delenumb=0;% 删除向量的个数  
  for j=1:bandsize
      zeronumb=0;%计数器，计0的个数，为4时即为一个零调度向量应删除
      for i=1:N
          if schedul(i,j)==0
              zeronumb=zeronumb+1;
          end
      end
      if zeronumb==4
          for k=j+1:bandsize-delenumb
              for t=1:N
                  schedul(t,k-1)=schedul(t,k);
              end
          end
          delenumb=delenumb+1;
          zeronumb=0;
      end
  end
  fprintf('\n先删除全零调度后的调度表为：');   schedul  
  delenumb     
  %%%%合并调度向量    
 
     schedullen=bandsize-delenumb; 
     schedultable=zeros(N,2);
     for i=1:N
         for j=1:schedullen
             schedultable(i,j)=schedul(i,j);
         end
     end
     fprintf('最终得到的调度表如下');schedultable  
     fprintf('size is');schedullen